BZOJ 3864 Hero meet devil (状压DP)

最近写状压写的有点多，什么$LIS,LCS$全都用状压写了…这道题就是一道状压$LCS$

---

题意

给出一个长度为$n(n<=15)$的字符串$s$，只由$A,T,G,C$组成。对于$0...n$的每一个$i$，求长度为$m(m<=1000)$且只由$A,T,G,C$组成的串中，有多少字符串与$s$的最长公共子序列$(LCS)$长度为$i$。

分析

• 先想想$LCS$的转移怎么写的，设$lcs(i,j)$表示长度为$m(m<=1000)$的未知串匹配到$i$，长度为$n(n<=15)$的$s$串匹配到$j$的最长公共子序列长度
  $large lcs(i,j)=left{ egin{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} ight.$可以观察到$lcs(i,j)$与$lcs(i,j-1)$的差最多为$1$，那么我们将$lcs(i,0...n-1)$的差分数组($01串$)状压，做$m$次转移来统计方案。差分数组的$1$的个数就是当前状态的$LCS$的长度。
• 可以预处理出每个状态后面加一个字符会得到的下一个状态。具体做法可以把差分数组还原成$lcs$数组再像普通的$LCS$来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
", 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();
}