DP套DP

DP套DP，就是将内层DP的结果作为外层DP的状态进行DP的方法。

[BZOJ3864]Hero meet devil

对做LCS的DP数组差分后状压，预处理出转移数组，然后直接转移即可。

tr[S][k]表示当前差分状压后的状态为S，加入字符k(k为ACGT中一个)后会转移到什么状态。

f[i][S]表示串已构造到第i位，和模式串的匹配状态差分后为S，的方案数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;

const int N=1010,M=50010,mod=1e9+7;
int T,n,m,d[20],g[20],ans[N],tr[M][4],cnt[M],f[2][M];
char s[20],c[10]="ACGT";

int main(){
    freopen("bzoj3864.in","r",stdin);
    freopen("bzoj3864.out","w",stdout);
    for (scanf("%d",&T); T--; ){
        scanf("%s%d",s+1,&m); n=strlen(s+1);
        for (int S=0; S<1<<n; S++){
            if (S) cnt[S]=cnt[S^(S&-S)]+1;
            rep(i,0,n-1) d[i+1]=d[i]+((S>>i)&1);
            rep(k,0,3){
                rep(i,1,n) g[i]=max(max(d[i],g[i-1]),(c[k]==s[i])?d[i-1]+1:0);
                tr[S][k]=0;
                rep(i,0,n-1) if (g[i+1]-g[i]) tr[S][k]|=1<<i;
            }
        }
        memset(ans,0,sizeof(ans)); memset(f,0,sizeof(f)); f[0][0]=1;
        rep(i,1,m){
            int v=i&1,u=v^1; memset(f[v],0,sizeof(f[v]));
            for (int S=0; S<1<<n; S++)
                rep(k,0,3) f[v][tr[S][k]]=(f[v][tr[S][k]]+f[u][S])%mod;
        }
        for (int S=0; S<1<<n; S++) ans[cnt[S]]=(ans[cnt[S]]+f[m&1][S])%mod;
        rep(i,0,n) printf("%d
",ans[i]);
    }
    return 0;
}

[BZOJ5336][TJOI2018]party

同上题，多加一维0/1/2表示末尾和'NOI'匹配到第几位即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;

const int N=1010,M=50010,mod=1e9+7;
int T,n,m,d[20],g[20],ans[N],tr[M][4],cnt[M],f[2][M][3];
char s[20],c[10]="NOI";

int main(){
    freopen("bzoj5336.in","r",stdin);
    freopen("bzoj5336.out","w",stdout);
    scanf("%d%d%s",&m,&n,s+1);
    for (int S=0; S<1<<n; S++){
        if (S) cnt[S]=cnt[S^(S&-S)]+1;
        rep(i,0,n-1) d[i+1]=d[i]+((S>>i)&1);
        rep(k,0,2){
            rep(i,1,n) g[i]=max(max(d[i],g[i-1]),(c[k]==s[i])?d[i-1]+1:0);
            tr[S][k]=0;
            rep(i,0,n-1) if (g[i+1]-g[i]) tr[S][k]|=1<<i;
        }
    }
    f[0][0][0]=1;
    rep(i,1,m){
        int v=i&1,u=v^1; memset(f[v],0,sizeof(f[v]));
        for (int S=0; S<1<<n; S++) rep(l,0,2) if (f[u][S][l]){
            rep(k,0,2){
                int S1=tr[S][k],l1=l;
                l1=(k==l) ? l1+1 : ((!k)?1:0);
                if (l1<3) f[v][S1][l1]=(f[v][S1][l1]+f[u][S][l])%mod;
            }
        }
    }
    for (int S=0; S<1<<n; S++)
        rep(i,0,2) ans[cnt[S]]=(ans[cnt[S]]+f[m&1][S][i])%mod;
    rep(i,0,n) printf("%d
",ans[i]);
    return 0;
}

[BZOJ3591]最长上升子序列

给出1~n的一个排列的一个最长上升子序列，求原排列可能的种类数。

考虑最长上升子序列$O(nlog n)$算法中使用的单调队列，将单调队列中的数组成的集合作为状态DP。

f[S]表示当前状态S的方案数，其中S是一个三进制数，第i位为0表示这个数尚未被选入数列，1表示选入数列但不在单调队列中，2表示在单调队列中。

对于每个状态，枚举下一个加入序列的数是什么来转移。可以先预处理减小常数。

具体细节可看代码注释，$O(2^n n^2+3^n n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=16,M=1.5e7;
int n,m,x,id[N],p[N],f[M];
bool flag[1<<N][N];
int v[1<<N][N],c[1<<N],mx[1<<N],s[1<<N],ans=0;

int main(){
    freopen("bzoj3591.in","r",stdin);
    freopen("bzoj3591.out","w",stdout);
    scanf("%d%d",&n,&m);
    rep(i,1,m) scanf("%d",&x),id[x-1]=i;
    p[0]=1; rep(i,1,n) p[i]=p[i-1]*3;
    for (int S=0; S<(1<<n); S++)//预处理出每个可能的状态转移，S为当前已经选进单调队列的集合，flag表示能否转移，v是转移到什么位置
        rep(i,0,n-1){
            if (S&(1<<i)){ c[S]+=p[i]; mx[S]=max(mx[S],i); s[S]++; continue; }
            //c:全1的三进制状态，mx:最大数，s:popcount
            if (!id[i]) flag[S][i]=1;
            else{
                int tot=0;
                rep(j,0,n-1) if (S&(1<<j) && id[j]) tot++;
                if (tot+1==id[i]) flag[S][i]=1;//满足在LIS中的位置为id[i]
            }
            int t=-1,x=0;
            rep(j,0,n-1) if (S&(1<<j)) x+=p[j];//S转三进制
            for (int j=n-1; j>i; j--) if (S&(1<<j)) t=j;//找到集合中比i大的最小的数更新
            if (~t) v[S][i]=x-p[t]+p[i]; else v[S][i]=x+p[i];
        }
    f[0]=1;
    for (int x=0; x<(1<<n); x++)
        for (int y=x; y>0 || (!y && !x); (!x) ? y-- : y=(y-1)&x)//x为已在序列中的数的集合，y为在单调队列中数的集合
            if (f[c[x]+c[y]]){
                int t=c[x]+c[y];
                for (int i=0; s[y]==m ? i<mx[y] : i<n; i++)//枚举新加进序列的数（若单调队列长度已满则不能加入更大的数）
                    if (flag[x][i]) f[c[x]+p[i]+v[y][i]]+=f[t];//新加进序列的数一定也加进单调队列
                if (x==(1<<n)-1) ans+=f[t];
            }
    printf("%d
",ans);
    return 0;
}