最近写状压写的有点多，什么LIS,LCSLIS,LCSLIS,LCS全都用状压写了…这道题就是一道状压LCSLCSLCS
题意
给出一个长度为n(n<=15)n(n<=15)n(n<=15)的字符串sss，只由A,T,G,CA,T,G,CA,T,G,C组成。对于0...n0...n0...n的每一个iii，求长度为m(m<=1000)m(m<=1000)m(m<=1000)且只由A,T,G,CA,T,G,CA,T,G,C组成的串中，有多少字符串与sss的最长公共子序列(LCS)(LCS)(LCS)长度为iii。
分析
- 先想想LCSLCSLCS的转移怎么写的，设lcs(i,j)lcs(i,j)lcs(i,j)表示长度为m(m<=1000)m(m<=1000)m(m<=1000)的未知串匹配到iii，长度为n(n<=15)n(n<=15)n(n<=15)的sss串匹配到jjj的最长公共子序列长度
lcs(i,j)={lcs(i−1,j−1)+1M[i]=s[j]Max(lcs(i−1,j),lcs(i,j−1))M[i]≠s[j]\large lcs(i,j)=\left\{
\begin{aligned}
&lcs(i-1,j-1)+1&M[i]=s[j]\\
&Max(lcs(i-1,j),lcs(i,j-1))&M[i]≠s[j]\\
\end{aligned}
\right.lcs(i,j)=⎩⎨⎧lcs(i−1,j−1)+1Max(lcs(i−1,j),lcs(i,j−1))M[i]=s[j]M[i]̸=s[j]可以观察到lcs(i,j)lcs(i,j)lcs(i,j)与lcs(i,j−1)lcs(i,j-1)lcs(i,j−1)的差最多为111，那么我们将lcs(i,0...n−1)lcs(i,0...n-1)lcs(i,0...n−1)的差分数组(01串01串01串)状压，做mmm次转移来统计方案。差分数组的111的个数就是当前状态的LCSLCSLCS的长度。 - 可以预处理出每个状态后面加一个字符会得到的下一个状态。具体做法可以把差分数组还原成lcslcslcs数组再像普通的LCSLCSLCS来DP，最后再还原。也可以像我这样直接写
for(int state = 0; state < (1<<n); ++state) //当前状态
for(int i = 0; i < 4; ++i) { //选哪一个字符
int res = 0, now = 0, pre = 0; //res存答案
for(int j = 0; j < n; ++j) {
int npre = pre + ((state>>j)&1);
int nnow = max(now, npre);
if(i == arr[j]) nnow = pre + 1;
if(nnow > now) res += 1<<j; //大于 说明此处差分数组值为1
pre = npre, now = nnow;
}
//pre:dp[i-1][j-1] npre:dp[i-1][j]
//now:dp[i][j-1] nnow:dp[i][j]
to[state][i] = res;
} - 注意清零啥的.
AC CODE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
const int MAXS = 32768;
const int mod = 1e9 + 7;
inline int num(char c) {
return c == 'A' ? 0 : c == 'T' ? 1 : c == 'G' ? 2 : 3;
}
char s[MAXN];
int n, m, arr[MAXN], ans[MAXN+1], to[MAXS][4], f[2][MAXS], sz[MAXS];
inline void solve() {
scanf("%s%d", s, &m); n = strlen(s);
for(int i = 0; i < n; ++i) arr[i] = num(s[i]);
for(int state = 0; state < (1<<n); ++state)
for(int i = 0; i < 4; ++i) {
int res = 0, now = 0, pre = 0;
for(int j = 0; j < n; ++j) {
int npre = pre + ((state>>j)&1);
int nnow = max(now, npre);
if(i == arr[j]) nnow = pre + 1;
if(nnow > now) res += 1<<j;
pre = npre, now = nnow;
}
//pre:dp[i-1][j-1] npre:dp[i-1][j]
//now:dp[i][j-1] nnow:dp[i][j]
to[state][i] = res;
}
int now = 0; f[now][0] = 1;
while(m--) { now ^= 1;
for(int state = 0; state < (1<<n); ++state) {
for(int i = 0; i < 4; ++i)
f[now][to[state][i]] = (f[now][to[state][i]] + f[now^1][state]) % mod;
f[now^1][state] = 0;
}
}
memset(ans, 0, sizeof ans);
for(int state = 0; state < (1<<n); ++state)
ans[sz[state]] = (ans[sz[state]] + f[now][state]) % mod, f[now][state] = 0;
for(int i = 0; i <= n; ++i)
printf("%d\n", ans[i]);
}
int main () {
int T;
for(int state = 0; state < MAXS; ++state)
sz[state] = sz[state>>1] + (state&1);
scanf("%d", &T);
while(T--) solve();
}