【BZOJ5336】[TJOI2018]party（动态规划）

题面

题解

这题好神仙啊。。。

考虑普通的\(LCS\)的\(dp\)，\(f[i][j]=\max\{f[i-1][j],f[i][j-1],f[i-1][j-1]+(A_i==B_j)\}\)

发现对于固定的\(i\)而言，随着\(j\)的增长，相邻的两个数之间的差不超过\(1\)，因此直接考虑一个\(2^k\)的状态记录差分的结果。

那么设\(f[i][S]\)表示当前考虑到了第\(i\)位，\(LCS\)的\(dp\)的差分数组为\(S\)的方案数。转移的时候枚举放那个字母就好了。因为还有连续字符的限制，所以再加一维就没有问题了。

这里转移因为会涉及差分数组的修改，所以可以提前把差分数组的转移给预处理出来，

然后大力\(dp\)就好了。

#include
    
     #include
     
      #include
      
       using namespace std;#define MOD 1000000007#define MAX 1010char ch[20],QwQ[5]="NOI";int f[2][1<<15][3],tr[1<<15][3],cnt[1<<15];int n,k,ans[MAX];void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}int dp[16],tmp[16];int Get(int S,int c){    for(int i=1;i<=k;++i)dp[i]=dp[i-1]+((S>>(i-1))&1);    for(int i=1;i<=k;++i)        if(QwQ[c]==ch[i])tmp[i]=dp[i-1]+1;        else tmp[i]=max(dp[i],tmp[i-1]);    int ret=0;    for(int i=1;i<=k;++i)ret|=(tmp[i]-tmp[i-1])<<(i-1);    return ret;}int main(){    scanf("%d%d",&n,&k);scanf("%s",ch+1);    for(int i=0;i<1<
       
        >1]+(i&1);    f[0][0][0]=1;    for(int i=1,nw=1,pw=0;i<=n;++i,nw^=1,pw^=1)    {        memset(f[nw],0,sizeof(f[nw]));        for(int j=0;j<1<