bzoj 3864: Hero meet devil

bzoj3864次元联通们

第一次写dp of dp (:з」∠) 不能再颓废啦

考虑最长匹配序列匹配书转移

由于dp[i][j]的转移可由上一行dp[i-1][j-1],dp[i-1][j],dp[i][j-1]得来

把dp[i]差分，得到一个01串

就可以用rans[s][ch]表示在状态s的dp数组后面接字符ch可以转移到的状态

枚举该转移就好了QAQ

/**************************************************************

    Problem: 3864

    Language: C++

    Result: Accepted

    Time:4208 ms

    Memory:2356 kb

****************************************************************/

//f[i]为之前前i项的LCS，g[i]为添加字母之后的

//g数组的差值就是下一次匹配转移到的状态

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::memset;

const int mod= 1000000007;

inline int read() {

	int x=0,f=1;

	char c=getchar() ;

	while(c<'0'||c>'9') {

		 if(c=='-')f=-1;

		 c=getchar();

	}

	while(c<='9'&&c>='0') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}const int maxn = 16;

int cnt,m,n;

char a[40];

int tans[1<<maxn][4];

int ans[2][1<<maxn],f[maxn],g[maxn];

int is[maxn];

int s[maxn];

void network(int maxx) {

	int now=1;

	memset(ans,0,sizeof ans);

	ans[0][0]=1;

	for(int i=1;i<=m;++i,now=i&1) {

		for(int j=0;j<4;++j)

			for(int e=0;e<maxx;++e)

				ans[now][tans[e][j]]=(ans[now][tans[e][j]]+ans[now^1][e])%mod;

		memset(ans[now^1],0,sizeof ans[now^1]);

		//now=i&1;

	}

	now^=1;

	memset(is,0,sizeof is);

	for(int i=0;i<maxx;++i) is[__builtin_popcount(i)]=(is[__builtin_popcount(i)]+ans[now][i])%mod;

	for(int i=0;i<=n;++i)printf("%d\n",is[i]);

}

void solve(int m,int n) {

	int maxx=1<<n;

	for(int i=0;i<maxx;++i) {

		f[0]=i&1;

		for(int j=1;j<n;++j) f[j]=((i>>j)&1)+f[j-1];

		for(int j=0;j<4;++j) {

			memset(g,0,sizeof g);

			for(int e=0;e<n;++e) {

				if(s[e]==j) g[e] = f[e-1]+1;//最后一位与原来匹配

				else g[e]=std::max(g[e-1],f[e]);

			}

			int tmp = 0;

			for(int e=0;e<n;++e)

				if(g[e]==g[e-1]+1)

					tmp|=1<<e;

			tans[i][j]=tmp;

		}

	}

	network(maxx);

}

int main() {

	cnt=read();

	for(int i=1;i<=cnt;++i) {

		scanf("%s",a);

		m=read();n=strlen(a);

		for(int i=0;i<n;++i)

			if(a[i]=='A') s[i]=0;

			else if(a[i]=='T') s[i]=1;

			else if(a[i]=='C') s[i]=2;

			else if(a[i]=='G') s[i]=3;

		solve(m,n);

	}

	return 0;

}

巴特西

bzoj 3864: Hero meet devil

最新文章

热门文章