题意：一段DNA序列s，只包含字符ATGC，长度不超过15，求有多少种长度为n的DNA序列与s的最长公共子序列长度为0~len。
解法：状压dp。
LSC：
if(a[i] == b[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
dp[i][j]表示分别以第i个元素和第j个元素结尾的待求字符串和已知字符串s的最长公共子序列。
对于本题，用dp[0]~dp[j]可以表示一种待求字符串的状态，可以进一步求出再添加一个字符后的状态。
例如：s为GTC
dp数组为[0, 1, 1]，说明最长公共子序列为T，加A后状态不变为011，加G后变为111，加T后不变，加C后变为012。
dp数组为非降序数列，所以可以在上升的位置置1，不变的位置置0，转化为二进制，例如状态011->010，012->011。
记录状态后，列出状态转移方程：
dp[i][j状态分别加四个字符后的状态] += dp[i - 1][j]。
i表示待求字符串长度，j表示状态，因为只与上一长度有关，所以可以用滚动数组优化。
代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
using namespace std;
const int mod = 1e9 + 7;
char dna[5] = "ATGC";
LL dp[2][70000], prt[20];
int res[20], res1[20], ans[70000][5];
int main()
{
int T;
while(~scanf("%d", &T))
while(T--)
{
memset(res, 0, sizeof res);
memset(ans, 0, sizeof ans);
memset(dp, 0, sizeof dp);
string s;
cin >> s;
int n;
cin >> n;
int len = s.size();
int maxx = 1 << len;
for(int i = 0; i < maxx; i++)
{
res[0] = 0;
int tmp = i;
int cnt = 1;
for(int j = 0; j < len; j++)//转化当前状态为正常dp
{
if(tmp & 1)
res[cnt] = res[cnt - 1] + 1;
else
res[cnt] = res[cnt - 1];
cnt++;
tmp >>= 1;
}
for(int j = 0; j < 4; j++)//计算分别加4个字符后状态变化
{
res1[0] = 0;
for(int k = 1; k <= len; k++)
{
if(s[k - 1] == dna[j])
res1[k] = res[k - 1] + 1;
else
res1[k] = max(res1[k - 1], res[k]);
}
for(int k = len; k > 0; k--)//记录i状态后添加字符j后的状态
{
ans[i][j] <<= 1;
if(res1[k] > res1[k - 1])
ans[i][j] += 1;
}
}
}
dp[0][0] = 1;
for(int i = 0; i < n; i++)
{
memset(dp[(i + 1) & 1], 0, sizeof dp[(i + 1) & 1]);
for(int j = 0; j < maxx; j++)
{
for(int k = 0; k < 4; k++)
{
dp[(i + 1) & 1][ans[j][k]] += dp[i & 1][j];
if(dp[(i + 1) & 1][ans[j][k]] > mod)
dp[(i + 1) & 1][ans[j][k]] %= mod;
}
}
}
memset(prt, 0, sizeof prt);
for(int i = 0; i < maxx; i++)
{
int cnt = 0;
int tmp = i;
while(tmp)
{
if(tmp & 1)
cnt++;
tmp >>= 1;
}
prt[cnt] += dp[n & 1][i];
if(prt[cnt] > mod)
prt[cnt] %= mod;
}
for(int i = 0; i <= len; i++)
printf("%lld
", prt[i]);
}
return 0;
}
运行了6s···
可以进行去掉无法达到的状态的优化···
不过写不动了···