M_sea

洛谷4590 [TJOI2018]游园会
LuoguLOJ分析DP 套 DP 。冷静分析一下题目中的几个限制:只包含 N,O,I不包含子串 NOI与一个模板...
扫描右侧二维码阅读全文
30
2019/06

洛谷4590 [TJOI2018]游园会

Luogu

LOJ

分析

DP 套 DP 。


冷静分析一下题目中的几个限制:

  • 只包含 N,O,I
  • 不包含子串 NOI
  • 与一个模板串的 LCS 为 $i$

考虑 DP 。第一个限制可以强制只加这三种字符,第二个限制可以多加一维 0/1/2 表示匹配了多少位,第三个限制可以建一个 LCS 自动机(?)然后在上面转移。


考虑这个自动机怎么建。

先回忆一下两个串的 LCS 怎么求。设 $dp[i][j]$ 表示两个串分别匹配到了第 $i$ 位、第 $j$ 位时的 LCS 长度,转移是 $dp[i][j]=\max\left\{dp[i-1][j],dp[i][j-1],d[i-1][j-1]+[A[i]=B[j]]\right\}$ 。

本题中一个串是固定的,那么转移一次只需要另一个串对应的字符以及前一维的 DP 数组。

注意到 $k\leq 15$ ,可以考虑把所有 DP 值作为自动机的一个节点,然后就可以对应的转移了。

但是这样子点数会非常多,考虑怎么优化。

可以发现 $dp[i]$ 这个数组是单调不降的,并且相邻两个数的差最多为 $1$ 。于是可以状压它的差分数组,点数就是 $2^k$ 级别的了。


然后剩下的就很简单了。设 $f[i][j][k]$ 表示前 $i$ 个字符,匹配到了自动机的 $j$ 节点,和 NOI 匹配了 $k$ 位的方案数,直接枚举填什么字符转移即可。


事实上可以不建出 LCS 自动机,而是每次 DP 时 DP 计算转移,因此这个东西被称为 DP 套 DP 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10,K=15+10;
const int mod=1e9+7;

int n,l,tot; char s[K];
int dp[2][K],f[2][1<<15][3],ans[K];

inline void add(int& x,int y) { x=(x+y)%mod; }

inline int encode() {
    int res=0;
    for (re int i=1;i<=l;++i)
        if (dp[1][i]-dp[1][i-1]) res|=1<<(i-1);
    return res;
}
inline void decode(int state) {
    for (re int i=1;i<=l;++i) dp[0][i]=(state>>(i-1))&1;
    for (re int i=1;i<=l;++i) dp[0][i]+=dp[0][i-1];
}

inline void trans(int i,int j,int k,char c,int w) {
    decode(j);
    for (re int p=1;p<=l;++p) {
        dp[1][p]=max(dp[1][p-1],dp[0][p]);
        dp[1][p]=max(dp[1][p],dp[0][p-1]+(c==s[p]));
    }
    add(f[i][encode()][k],w);
}

int main() {
    n=read(),l=read(),tot=1<<l,scanf("%s",s+1);
    f[0][0][0]=1;
    for (re int i=0;i<n;++i) {
        int now=i&1,nxt=now^1;
        memset(f[nxt],0,sizeof(f[nxt]));
        for (re int j=0;j<tot;++j) {
            if (f[now][j][0]) {
                trans(nxt,j,1,'N',f[now][j][0]);
                trans(nxt,j,0,'O',f[now][j][0]);
                trans(nxt,j,0,'I',f[now][j][0]);
            }
            if (f[now][j][1]) {
                trans(nxt,j,1,'N',f[now][j][1]);
                trans(nxt,j,2,'O',f[now][j][1]);
                trans(nxt,j,0,'I',f[now][j][1]);
            }
            if (f[now][j][2]) {
                trans(nxt,j,1,'N',f[now][j][2]);
                trans(nxt,j,0,'O',f[now][j][2]);
            }
        }
    }
    for (re int i=0;i<tot;++i)
        for (re int j=0;j<=2;++j)
            add(ans[__builtin_popcount(i)],f[n&1][i][j]);
    for (re int i=0;i<=l;++i) printf("%d\n",ans[i]);
    return 0;
}
最后修改:2019 年 08 月 14 日 08 : 13 AM

2 条评论

  1. yzhang

    话说f数组也是要滚动的吧,您在开数组时多开了吧,我看会MLE(

    1. M_sea
      @yzhang

      您说的是

发表评论