相似

在看這道題前，有必要先看一下DP套DP的入門題[uoj3864]Hero meet devil，附上兩篇寫得不錯的題解：
https://blog.csdn.net/Ike940067893/article/details/87863041
https://www.cnblogs.com/RabbitHu/p/BZOJ3864.html

• 可以發現，$S$和$T$相似，等價于它們的最長公共子序列長度至少為$n?k$
• 考慮如何求兩個字符串的LCS。設 $lc{s}_{i,j}$ 表示 $S[1...i]$ 與 $T[1...j]$ 的 LCS 長度，轉移顯然為
  $$lc{s}_{i,j}=\{\begin{array}{rl}& lc{s}_{i?1,j?1}+1(S[i]==T[j])\\ & max\{lc{s}_{i?1,j},lc{s}_{i,j?1}\}(S[i]!=T[j])\end{array}$$
• 考慮如何拓展到$T$任意的情況。自然的想法是DP套DP：設$dp[j][lc{s}_{1,j},lc{s}_{2,j},...,lc{s}_{n,j}]$表示 考慮到$T$的前$j$位，$lc{s}_{?,j}$的情況如第二維所示 的方案數
• 直接這樣維護狀態肯定是行不通的，考慮優化：
  1.發現 $lc{s}_{i,j}?lc{s}_{i?1,j}\in \{0,1\}$，那么 $lc{s}_{1,j},lc{s}_{2,j},...,lc{s}_{n,j}$的差分數組必是一個01 串 ，我們 狀壓這個01串 來描述第二維的狀態
  2.$n$位01串還是太大了，考慮如何利用$k$很小這個性質進行優化。
  $考慮某個lc{s}_{i,j}，若|i?j|>k，那么在轉移到lc{s}_{n,n}時，必然值不超過lc{s}_{i,j}+min\{n?i,n?j\}<=min\{i,j\}+min\{n?i,n?j\}=n?|i?j|<n?k$
  因此這樣的$lc{s}_{i,j}$是沒用的，可以直接丟掉，即對于每個$j$，我們只需要記錄$lc{s}_{j?k,j},lc{s}_{j?k+1,j},...,lc{s}_{j+k,j}$
  3.只知道$lc{s}_{j?k,j}$~$lc{s}_{j+k,j}$的差分數組，我們是無法知道它們的實際值的，因此考慮開多一維來記錄$lc{s}_{j,j}$的實際值以推出其它的$lcs$值，即我們設$dp[j][x][s]$表示 考慮到$T$的前$j$位，$lc{s}_{j,j}==x$，$lc{s}_{j?k,j},lc{s}_{j?k+1,j},...,lc{s}_{j+k,j}$的差分數組狀壓后為$s$ 的方案數
  4.$\because lc{s}_{n,n}\in [n?k,n](即不匹配的字符最多k個)$
  $\therefore ?j\in [1,n]滿足lc{s}_{j,j}\in [j?k,j]$，所以我們可以將$dp$的第二維設置為$lc{s}_{j,j}?(j?k)=lc{s}_{j,j}?j+k$，即$dp[][x][]$表示$lc{s}_{j,j}?j+k==x$，這樣就令$x\in [0,k]$
• 考慮如何實現狀態轉移。$dp$數組的第三維不好直接得到，我們考慮把它預處理出來：設$p[i][j][s1][c]$表示考慮到$T$的前$i$位，$lc{s}_{i,i}==j$（知道$lc{s}_{i,i}$就可以通過差分數組推出其它的$lcs$值），$lc{s}_{i?k,i},lc{s}_{i?k+1,i},...,lc{s}_{i+k,i}$的差分數組狀壓后為s1，在$T$的$i+1$位新增字符$c$后，$lc{s}_{i+1?k,i+1},lc{s}_{i+2?k,i+1},...,lc{s}_{i+1+k,i+1}$狀壓完的差分數組
• 同樣，需要優化$p$的狀態設置：
  1.同上，我們可以將$p$的第二維設置為$lc{s}_{i,i}?(i?k)=lc{s}_{i,i}?i+k$，即$p[][j][][]$表示$lc{s}_{i,i}?i+k==j$，這樣就令$j\in [0,k]$
  2.其實$p$轉移到的新差分數組狀態與新增字符具體是什么無關，與新增字符與S每一位的匹配情況有關。再進一步地，
  $\because lc{s}_{h,h}\in [h?k,h]$
  $\therefore T[h]只可能與S[h?k]$~$S[h+k]匹配$，即我們只需要考慮新增字符與$S[i+1?k]$~$S[i+1+k]$的匹配情況。直接把第四維設置成這個匹配情況即可。
  3.仔細想想，把第四維改成匹配情況后，$p$的轉移已經與第一維無關了，直接刪掉即可

至此，這道題就可以實現了

#include<iostream> #include<cstdio> #include<cstring> #define mod 998244353 using namespace std; typedef pair<int,int> pr; const int N=30001; const int K=5; const int S=256; int n,m,ans,dp[N][K][S],f[31],g[31]; pr p[K][S][S<<1]; char ch[N]; bool flag[31]; int add(int a,int b){a=a+b;if(a>mod) a-=mod;return a; } int mul(int a,int b){return 1ll*a*b%mod; } void dfs(int a,int b,int c){if(dp[a][b][c]==0) return;int l=max(a-m,0),r=min(a+m,n-1),sz=26;for(int i=l;i<=r;i++){if(!flag[ch[i+1]-'A']){flag[ch[i+1]-'A']=1;sz--;}f[ch[i+1]-'A']|=(1<<(i-a+m));//統計每種字符的匹配情況 }for(int i=l;i<=r;i++){if(flag[ch[i+1]-'A']){int x=p[b][c][f[ch[i+1]-'A']].first;int y=p[b][c][f[ch[i+1]-'A']].second;if(x>=0) dp[a+1][x][y]=add(dp[a+1][x][y],dp[a][b][c]);flag[ch[i+1]-'A']=0;f[ch[i+1]-'A']=0;}}int x=p[b][c][0].first,y=p[b][c][0].second;if(x>=0) dp[a+1][x][y]=add(dp[a+1][x][y],mul(dp[a][b][c],sz)); } int main(){scanf("%s%d",ch+1,&m);n=strlen(ch+1);//省略一維l，表示考慮到第l位 for(int i=0;i<=m;i++){//lcs[l][l]-l+m==i for(int j=0;j<(1<<(2*m));j++){//lcs[l-m][l]~lcs[l+m][l]的差分數組狀壓 for(int k=0;k<(1<<(2*m+1));k++){//T[l+1]與S[l+1-m]~S[l+1+m]匹配情況狀壓 //f:(lcs[l-m][l]-l+m)~(lcs[l+m][l]-l+m) //g:(lcs[l+1-m][l+1]-l+m)~(lcs[l+1+m][l+1]-l+m)f[m]=i;for(int a=m-1;a>=0;a--) f[a]=f[a+1]-(j>>a&1);for(int a=m;a<2*m;a++) f[a+1]=f[a]+(j>>a&1);for(int a=0;a<=2*m;a++){if((k>>a)&1) g[a+1]=max(f[a]+1,f[a+1]);//匹配else g[a+1]=max(f[a],f[a+1]); //不匹配 g[a+1]=max(g[a],g[a+1]);}int x=g[m+1]-1;//x=lcs[l+1][l+1]-(l+1)+mint y=0;if(x>=0){for(int a=m-1;a>=0;a--) if(g[a+1]^g[a+2]) y|=1<<a;for(int a=m;a<2*m;a++) if(g[a+1]^g[a+2]) y|=1<<a;}p[i][j][k]=make_pair(x,y);}}}//預處理 for(int i=0;i<=30;i++) f[i]=0;dp[0][m][0]=1;for(int i=0;i<n;i++){//考慮到第i位 for(int j=0;j<=m;j++){//lcs[i][i]-i+m==j for(int k=0;k<(1<<(2*m));k++){//差分數組狀壓 dfs(i,j,k);}}}//dpfor(int i=0;i<=m;i++){for(int j=0;j<(1<<(2*m));j++){ans=add(ans,dp[n][i][j]);}}printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的[XSY] 相似（DP套DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。