dp套dp的板子题

对于我这种垃圾来说：神仙题

考虑到最长公共子序列的dp做法

\(dp[i][j]=max{dp[i-1][j],dp[i][j-1],dp[i-1}[j-1]+(a[i]==b[i])\)

然后发现对于一种状态，我们只需要考虑当前这个字符填的是什么就好了

那么这个状态怎么存下来呢，差分之后就可以状压啦

考虑设\(f[i][j][k]\)表示当前到第\(i\)个字符，状态为\(j\)，当前匹配到第\(k\)位的方案数

由于会炸空间，第一维要滚动

代码：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;void read(int &x){    char ch;bool ok;    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}#define rg registerconst int mod=1e9+7;int ans[20],n,k,f[2][1<<15][3],a[1<<15],b[1<<15],s[1<<15][3],m;char ch[20],d[3]={'N','O','I'};int prepare(int s,int w){    memset(b,0,sizeof b);    for(rg int i=1;i<=k;i++)a[i]=a[i-1]+((s>>(i-1))&1);    for(rg int i=1;i<=k;i++){        if(d[w]==ch[i])b[i]=a[i-1]+1;        else b[i]=max(a[i],b[i-1]);    }    int ans=0;    for(rg int i=1;i<=k;i++)ans|=(b[i]-b[i-1])<<(i-1);    return ans;}int get_size(int x){int ans=0;while(x)ans+=x&1,x>>=1;return ans;}int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}signed main(){    read(n),read(k),scanf("%s",ch+1),m=1<