CLS好早的題了。。。非常經典啊。。。
　題意：給定長度為n的串S，求有多少個長度為m的串T使得LCS(S,T)分別為0,1...n。

　我們希望能夠用一個f[j][{lcs[1][j],lcs[2][j],lcs[3][j]...lcs[n][j]}]來表示當前狀態(tài)以計算答案。
　一開始似乎會嘗試直接用子序列來直接容斥。。。會發(fā)現這樣很難搞，也不太對。。于是回到LCS的計算上看看有什么性質可以用。
　　

LCS[i][j]=max{LCS[i?1][j],LCS[i][j?1],　　[S[i]==T[j]]?(LCS[i?1][j?1]+1)}
　　注意到在這個DP矩陣里面，任意相鄰的兩格的差至多為1，這樣我們就可以用一個狀壓將相鄰格子的差搞起來，以此表示 T串到第j位時的LCS狀態(tài)。
　　而對于狀態(tài)之間的轉移，可以先枚舉上一行的 LCS狀態(tài)，算出來之后枚舉當前行會和什么字符匹配，以計算出當前行的 LCS狀態(tài)，并得到狀壓的狀態(tài)。簡單地預處理一下就可以只枚舉當前行的匹配字符來快速完成轉移了。
　　預處理的復雜度為 O(n2n)，DP復雜度為 O(m2n)。
　　感覺這東西要講清楚有點麻煩呢。。。

　　
丑的一B的代碼：

/*I will chase the meteor for you, a thousand times over.Please wait for me, until I fade forever.Just 'coz GEOTCBRL. */ #include <bits/stdc++.h> using namespace std; #define fore(i,u) for (int i = head[u] ; i ; i = nxt[i]) #define rep(i,a,b) for (int i = a , _ = b ; i <= _ ; i ++) #define per(i,a,b) for (int i = a , _ = b ; i >= _ ; i --) #define For(i,a,b) for (int i = a , _ = b ; i < _ ; i ++) #define Dwn(i,a,b) for (int i = ((int) a) - 1 , _ = (b) ; i >= _ ; i --) #define fors(s0,s) for (int s0 = (s) , _S = s ; s0 ; s0 = (s0 - 1) & _S) #define foreach(it,s) for (__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)#define mp make_pair #define pb push_back #define pii pair<int , int> #define fir first #define sec second #define MS(x,a) memset(x , (a) , sizeof (x))#define gprintf(...) fprintf(stderr , __VA_ARGS__) #define gout(x) std::cerr << #x << "=" << x << std::endl #define gout1(a,i) std::cerr << #a << '[' << i << "]=" << a[i] << std::endl #define gout2(a,i,j) std::cerr << #a << '[' << i << "][" << j << "]=" << a[i][j] << std::endl #define garr(a,l,r,tp) rep (__it , l , r) gprintf(tp"%c" , a[__it] , " \n"[__it == _])template <class T> inline void upmax(T&a , T b) { if (a < b) a = b ; } template <class T> inline void upmin(T&a , T b) { if (a > b) a = b ; }typedef long long ll;const int maxn = 100007; const int maxm = 200007; const int maxs = 1 << 16; const int mod = 1000000007; const int inf = 0x7fffffff; const double eps = 1e-7;typedef int arr[maxn]; typedef int adj[maxm];inline int fcmp(double a , double b) {if (fabs(a - b) <= eps) return 0;if (a < b - eps) return -1;return 1; }inline int add(int a , int b) { return ((ll) a + b) % mod ; } inline int mul(int a , int b) { return ((ll) a * b) % mod ; } inline int dec(int a , int b) { return add(a , mod - b % mod) ; } inline int Pow(int a , int b) {int t = 1;while (b) {if (b & 1) t = mul(t , a);a = mul(a , a) , b >>= 1;}return t; }#define gc getchar #define idg isdigit #define rd RD<int> #define rdll RD<long long> template <typename Type> inline Type RD() {char c = getchar(); Type x = 0 , flag = 1;while (!idg(c) && c != '-') c = getchar();if (c == '-') flag = -1; else x = c - '0';while (idg(c = gc()))x = x * 10 + c - '0';return x * flag; } inline char rdch() {char c = gc();while (!isalpha(c)) c = gc();return c; } #undef idg #undef gc// beginning#define shl(x) (1 << (x))const char ch[] = {'A' , 'C' , 'G' , 'T'};int n , m , all; int bcnt[maxs] , trans[maxs][4]; int f[2][maxs];char S[16];void input() {scanf("%s" , S + 1);n = strlen(S + 1) , m = rd();all = shl(n); }inline void init_trans() {static int pre[16] , cur[16];For (s , 0 , all) {if (s)bcnt[s] = bcnt[s >> 1] + (s & 1);For (i , 0 , n) pre[i + 1] = pre[i] + (s >> i & 1);rep (c , 0 , 3) {int t = 0;cur[0] = 0;rep (i , 1 , n) {cur[i] = max(cur[i - 1] , pre[i]);if (S[i] == ch[c]) upmax(cur[i] , pre[i - 1] + 1);t |= (cur[i] - cur[i - 1]) << (i - 1);}trans[s][c] = t;}} }#define upd(a,b) a = add(a , b)void solve() {int cur = 0 , nxt = 1;init_trans();memset(f[cur] , 0 , all << 2);f[0][0] = 1;For (i , 0 , m) {memset(f[nxt] , 0 , all << 2);For (s , 0 , all) if (f[cur][s]) For (c , 0 , 4)upd(f[nxt][trans[s][c]] , f[cur][s]);cur ^= 1 , nxt ^= 1;}static int ans[16];rep (i , 0 , n) ans[i] = 0;For (s , 0 , all)upd(ans[bcnt[s]] , f[cur][s]);rep (i , 0 , n) printf("%d\n" , ans[i]); }int main() {#ifndef ONLINE_JUDGEfreopen("data.txt" , "r" , stdin);#endifrep (T , 1 , rd()) {input();solve();}return 0; }

總結

以上是生活随笔為你收集整理的【bzoj 3864】Hero meets devil - DP套DP的全部內容，希望文章能夠幫你解決所遇到的問題。

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