首先，LCS是可以在O(nlogn)下求出來(lái)的，只要將A串的元素x替換成x在B串中出現(xiàn)的所有位置的降序，最后求修改后的A串的LIS就可以了。
因?yàn)?span id="ze8trgl8bvbq" class="MathJax_Preview">n很小，就可以直接狀壓維護(hù)在O(nlogn)求LIS時(shí)記錄某個(gè)長(zhǎng)度的子序列的最小結(jié)尾的數(shù)組了（如果該數(shù)出現(xiàn)，則置1）。預(yù)處理一下每個(gè)狀態(tài)遇到A，T，C，G四個(gè)字母時(shí)會(huì)轉(zhuǎn)變的狀態(tài)，之后遞推即可。

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define clr(a) memset(a,0,sizeof(a)) typedef long long ll; const ll md=1000000007;ll dp[2][70000],rs[1001]; char cz[20],tz[4]={'A','T','C','G'};int n,m,ts[70000][4]; int _le(int x){int r=0;for(;x;x>>=1)r+=(x&1);return r;}; int _cl(int x,int a){if(x&(1<<a))return x;for(a=1<<a,x^=a,a<<=1;x>=a&&!(x&a);a<<=1);return x&a?x^a:x; }; void cl(){int i,j,a,b,d,c,q,t;scanf("%s %d",cz,&m);n=strlen(cz);clr(dp),c=0,q=1,dp[0][0]=1;for(d=1<<n,i=0;i<d;++i)for(j=0;j<4;++j){for(t=i,b=n-1;b>=0;--b)if(cz[b]==tz[j])t=_cl(t,b);ts[i][j]=t;}for(i=0;i<m;++i,swap(c,q))for(clr(dp[q]),a=0;a<d;++a)for(j=0;j<4;++j){dp[q][t=ts[a][j]]+=dp[c][a];if(dp[q][t]>=md)dp[q][t]-=md;}for(clr(rs),i=0;i<d;++i){rs[a=_le(i)]+=dp[c][i];if(rs[a]>=md)rs[a]-=md;}for(i=0;i<=n;printf("%I64d\n",rs[i++])); }; int main(){ #ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout); #endifint t;scanf("%d",&t);while(t--)cl();return 0; };

總結(jié)

以上是生活随笔為你收集整理的hdu 4899 Hero meet devil的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。