题解 P4590 【[TJOI2018]游园会】

· · 题解

一个有趣的技术名字叫做dp套dp

基本是道板子题，只是注意直接开这么大的数组会炸请注意使用滚动数组进行优化

首先翻译一下并不好懂的题意

题目的意思是对于每一个i求满足如下条件的字符串的数目

1.长度为n且只出现过'N','O','I'三种字符

2.和一个长度为k的模式串的最长公共子序列长度恰好为i

3.不含"NOI"这个子串

然后这是一道对于字符串进行计数的题目那么我们考虑采取设一个dp_{i,……}表示长度为i，处于一些奇奇怪怪的状态时字符串的方案数，这样的话我们的转移就是枚举下一位是填'N'还是填'O'还是填'I'了，这样做有一个好处是你dp的时候不需要考虑有没有字符串被重复计数了，因为你的转移保证了每个字符串最多被dp到一次，坏处就是别的限制几乎就只能求助于dp的额外维度了

对于字符串题的话我们满足别的限制基本就是建一个自动机来搞定别的限制条件……像什么Ac自动机后缀自动机之类的都可以帮我们搞定一些但不是全部的限制条件

但是呢，没有"NOI”子串这个限制条件我们似乎可以轻松的记一维k \in \{0,1,2\}表示这个字符串匹配‘NOI’的长度来轻松搞定

但是……和一个模式串的最大子序列长度恰好为i这个限制条件就变得辣手了，因为我们并没有一个类似于“最大子序列自动机”的东西

但是仔细想想真的没有嘛？

除了自动机，还有什么东西是可以通过每次加一个字符实现转移的呢……?

当然是dp了~

所以让我们来考虑一下两个串求最长公共子序列的过程

设dp_{i,j}表示在第一个串A长度为i的前缀和第二个串B长度为j的前缀的最长公共子序列长度

那么我们可以得到一个转移方程是

dp_{i,j}=max(dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+(A_{i}==B_{j}))

接下来我们对这个转移方程以及dp数组做若干手脚，人工制造出一个“最长子序列自动机”来

首先我们认为B这个字符串是已知的这样的话我们就会发现我们每次转移所需要的东西有两个，一个是dp_{i-1}这个一维数组，另一个是A串的第i个字符了，有了这两个东西我们就可以根据转移方程构造出dp_{i}这个数组来

那么假设B串的长度不是非常长，那么此时我们可以直接将一个长度为|B|的数组看成自动机上的一个节点，这样的话我们就可以强行把刚才的转移方程当做自动机的转移条件，此时我们要做的就是枚举dp_{i-1}数组每一个可能的形态，然后枚举每一个可能的字符，根据转移方程计算出对应的转移到的数组dp_{i}这样我们就初步建成了一个“最长子序列自动机”，当然节点数非常非常多就是了

现在的瓶颈明显出在我们需要将一个数组视为子序列自动机的一个节点这个问题上 我们需要考虑一下是不是所有的dp数组都是合法的

然后我们认真的考虑一下发现有很大一部分数组是不合法的

因为dp_{i,j}表示两个字符串前缀的的最长公共子序列长度因此我们发现一个有趣的事实是对于任意字符串A和任意的i数组dp_{i}一定是单调的，另一个信息是，由于是最长公共子序列，所以数组dp_{i}任意两项的差要么是0要么是1，此时我们就可以将这个原数组的差分数组表达成一个01串，现在所有可能合法的dp数组和所有的01串11对应，然后把这个01串状压起来，我们就得到一个节点数为2^k的最长子序列自动机

然后还是老样子枚举点枚举出边字符使用dp的转移方程计算转移点就可以了

此时我们就可以设dp_{i,j,k}表示长度为i的字符串，处在子序列自动j号点上，以及匹配"NOI"的长度是k时符合条件字符串的个数

然后无脑的跑一边dp就行了

当然，你可以不必把自动机建出来，而是每次转移的时候现场dp一次计算转移到的状态，这样也是可以通过本题的(6000ms时限随便过)这也是这种技术被称为dp套dp的原因

好了代码实际上是比你想象的好写的

上代码

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e3+10;typedef long long ll;const ll mod=1e9+7;
int n;int k;char mde[100];int dp[2][35000][3];int tr1[100];int tr2[100];int siz[35000];ll ans[100];
inline int hsh(int* a){int ret=0;for(int i=0;i<k;i++)ret|=(a[i+1]-a[i])<<i;return ret;}
inline void dhsh(int* a,int ret)//数组和数之间的转化
{
    for(int i=0;i<k;i++)a[i+1]=(ret>>i)&1;
    for(int i=1;i<=k;i++)a[i]+=a[i-1];
}
inline void dypr(int ti,int cf,int tj,char c,const ll& val)//转移函数
{
    dhsh(tr1,cf);//现场解压数组之后压缩
    for(int i=1;i<=k;i++)tr2[i]=max(max(tr2[i-1],tr1[i]),tr1[i-1]+1*(c==mde[i]));
    int tcf=hsh(tr2);(dp[ti][tcf][tj]+=val)%=mod;
}
int main()
{
    scanf("%d%d",&n,&k);scanf("%s",mde+1);//注意滚动数组
    for(int i=1;i<=32767;i++)siz[i]+=siz[i>>1]+(i&1);dp[0][0][0]=1;
    for(int i=0;i<n;i++)
    {
        int ti=(~i)&1;int ni=i&1;
        for(int j=0;j<(1<<k);j++)
            for(int p=0;p<3;p++)dp[ti][j][p]=0;
        for(int j=0;j<(1<<k);j++)//暴力枚举下一个字符进行转移
        {
            if(dp[ni][j][0]!=0)
            {
                dypr(ti,j,1,'N',dp[ni][j][0]);
                dypr(ti,j,0,'O',dp[ni][j][0]);
                dypr(ti,j,0,'I',dp[ni][j][0]);
            }
            if(dp[ni][j][1]!=0)
            {
                dypr(ti,j,1,'N',dp[ni][j][1]);
                dypr(ti,j,2,'O',dp[ni][j][1]);
                dypr(ti,j,0,'I',dp[ni][j][1]);
            }
            if(dp[ni][j][2]!=0)
            {
                dypr(ti,j,1,'N',dp[ni][j][2]);
                dypr(ti,j,0,'O',dp[ni][j][2]);
            }
        }
    }
    for(int i=0;i<(1<<k);i++)//最长子序列长度自然就是01串中1的个数，因为这是dp数组中的最大值
        for(int p=0;p<3;p++)(ans[siz[i]]+=dp[n&1][i][p])%=mod;
    for(int i=0;i<=k;i++)printf("%lld\n",ans[i]);return 0;//拜拜程序~
}