题解：P4590 [TJOI2018] 游园会

· · 题解

DP 套 DP 的板子题，但我们可以在大家都会的做法上再优化一点。

大家都知道 LCS 的 DP 方程：f_{i,j} 表示奖章串前 i 位和兑奖串前 j 位的 LCS，转移大家都会就不讲了。

然后观察性质发现同一行 f_{i} 满足 f_{i,j}-f_{i,j-1}\in \{0,1\}。我们就能直接把一维压成一个二进制数然后 DP 就行了，这样预处理转移可以做到 O(n2^k)，这个其他题解都提过，DP 套 DP 怎么转移其实就是一个简单的自动机上 DP，枚举状态和转移边即可，我们就不细讲了，可以看我的代码。

但是我们知道 DP 套 DP 的状态数不要脑测，比如麻将和移除石子的状态数看着是指数级别的但是搜出来只有几千，这题是类似的。

我们借鉴之前解法压缩状态的做法然后直接 dfs 一下搜索合法状态，发现随机输入几个长 15 的串只有 1000\sim 2000 的状态数，实际测下来状态数不超过 6000，而且随机串数据下很难卡满，比直接状压 2^{k} 的数组状态数要小太多了。

放一下搜状态的代码：

int dfs(int sta){
    if(vis[sta]) return vis[sta];
    vis[sta]=++tot;

    auto work=[&](int to,char c)->void{
        rep(i,1,k) g[0][i]=g[0][i-1]+((sta>>(i-1))&1);
        len[vis[sta]]=g[0][k];
        int nxt=0;
        rep(i,1,k){
            g[1][i]=max(g[0][i],g[1][i-1]);
            if(s[i]==c) g[1][i]=max(g[1][i],g[0][i-1]+1);
            nxt|=((g[1][i]-g[1][i-1])<<(i-1));
        }
        trans[vis[sta]][to]=dfs(nxt);
    };

    work(0,'N');
    work(1,'O');
    work(2,'I');

    return vis[sta];
}

这样我们就做到了 O( n|\Sigma|) 的复杂度，其中 |\Sigma| 为搜出来 LCS 数组的状态数，当然有一个 9 倍的常数。

这样跑得飞快，加了取模优化后最慢点 35ms，成功拿下最优解（2024.7.16）。

代码：

const int N=1e3+100,M=6005+100,mod=1e9+7;
int n,k,f[2][M][3],g[2][20],trans[M][3],vis[1<<15],len[M],tot;
string s;
int dfs(int sta){//搜状态
    if(vis[sta]) return vis[sta];
    vis[sta]=++tot;

    auto work=[&](int to,char c)->void{
        rep(i,1,k) g[0][i]=g[0][i-1]+((sta>>(i-1))&1);
        len[vis[sta]]=g[0][k];
        int nxt=0;
        rep(i,1,k){
            g[1][i]=max(g[0][i],g[1][i-1]);
            if(s[i]==c) g[1][i]=max(g[1][i],g[0][i-1]+1);
            nxt|=((g[1][i]-g[1][i-1])<<(i-1));
        }
        trans[vis[sta]][to]=dfs(nxt);
    };

    work(0,'N');
    work(1,'O');
    work(2,'I');

    return vis[sta];
}
void _add(int &u,int v){
    u=(u+v>=mod)?u+v-mod:u+v;
}
int ans[25];
signed main(){
    read(n,k);
    cin>>s;s=' '+s;
    dfs(0);
    f[0][vis[0]][0]=1;
    rep(i,0,n-1){
        int o=i&1;
        rep(j,1,tot){//枚举状态
            if(f[o][j][0]){
                _add(f[o^1][trans[j][0]][1],f[o][j][0]);//加一个 N
                _add(f[o^1][trans[j][1]][0],f[o][j][0]);//加一个 O
                _add(f[o^1][trans[j][2]][0],f[o][j][0]);//加一个 I
            }
            if(f[o][j][1]){
                _add(f[o^1][trans[j][0]][1],f[o][j][1]);//加一个 N
                _add(f[o^1][trans[j][1]][2],f[o][j][1]);//加一个 O
                _add(f[o^1][trans[j][2]][0],f[o][j][1]);//加一个 I
            }
            if(f[o][j][2]){
                _add(f[o^1][trans[j][0]][1],f[o][j][2]);//加一个 N
                _add(f[o^1][trans[j][1]][0],f[o][j][2]);//加一个 O
                //不能加 I，不然就变成 NO+I 出现 NOI 了
            }
            f[o][j][0]=f[o][j][1]=f[o][j][2]=0;
        }
    }
    rep(j,1,tot) rep(k,0,2) _add(ans[len[j]],f[n&1][j][k]);
    rep(i,0,k) write(ans[i],'\n');
    return 0;
}