T10 Hero meet devil (HDU4899)

苹果蓝17 · 2020-04-27 10:27:52 · 个人记录

T10 Hero meet devil (HDU4899)

HDU传送门

题意简述

给出一个字符串 S ，这个字符串只由 'A' , 'C' , 'G' , 'T' 四个字母组成。

对于 0~|S| 中的每一个 i ，求出满足以下条件的字符串 T 的个数：

• 1.长度为 m ；

• 2.只由 'A' , 'C' , 'G' , 'T' 四个字母组成；

• 3.LCS(S,T)=i。

答案对 1e9+7 取模后输出

• 延伸：对于长度为m的，随机的，由 'A' , 'C' , 'G' , 'T' 构成的字符串，求它与 S 的 LCS 期望值

数据范围

(其实可以跑进1s，原题没这么卡不过一样的)

题解

思路

那么有

dp[i][j]=dp[i-1][j-1]+1 (s[i]==t[j]) dp[i][j]=max(dp[i-1][j],dp[i][j-1]) (s[i]!=t[j])

这样可以得到一个 dp 矩阵

那怎么去计数呢？

回到多个 T 上

虽然 T 是不固定的，但是 S 是固定的

也就是说，不管 T 是多少，矩阵的行数总是 |S| 不变

当然我们只关心最后一列（即 dp[i][|T|]）

那对于一个确定的 |T| 来说，只有最后一列是真正有用的，而它只有 |S|<=15 个数，每个数也不超过 15

所以最多也只有这么多种状态，很好统计

可以考虑以最后一列为状态再进行一次dp，这次存储的就是方案数了

可 15 个数的状态有多少种呢……

先不说怎么打了， 15^{15} 肯定炸了吧

但是真的有这么多种状态吗？

观察发现，它肯定是单调不减的

而且相邻两位之间差绝对值不超过 1

因为多加一位， LCS 不可能多出2位啊

所以我们就可以状压了嘛，把差分数组压成二进制

那这个大小就只有 2^{15}=32768 ，好写省时省空间~

做法

设 f[i][mac] 为长度为i的字符串， LCS DP矩阵最后一列为mac的方案数

（这里mac可以理解成15个数）

转移就很简单了，相当于在结尾加一个字符

等等，那加一个字符mac怎么变呢？

显然用前面 LCS 的朴素算法就行了

预处理一个 trans[mac][i] 数组，就很快了

预处理时间复杂度 O(|S|2^{|S|})

答案怎么统计？

设 las_{mac} 表示 mac 的最后一个数（即dp[|S|][|T|]）

时间复杂度 O(m2^{|S|})

总时间复杂度 O(T(|S|+m)2^{|S|})，可以跑进 1s

注意事项

• 初始化 f[0][0]=1

• 这题卡空间，把 f 滚动一下即可

AC代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,m;
char s[16];
int q[16],trans[33000][5],f[2][33000],ans[16];
void tran(int mac,int k){
    int a[16]={},b[16]={};//记得清零 
    for(int i=1;i<=n;i++) a[i]=a[i-1]+((mac>>(i-1))&1);
    //把状压差分打开 
    for(int i=1;i<=n;i++){
        if(k!=q[i]) b[i]=max(b[i-1],a[i]);
        if(k==q[i]) b[i]=max(b[i],a[i-1]+1);
    }//按照朴素LCS的转移 
    for(int i=1;i<=n;i++) trans[mac][k]|=((b[i]-b[i-1])<<(i-1));
    //把数组化成状压差分 
}
void pre(){
    for(int j=0;j<=(1<<n)-1;j++)
        for(int k=1;k<=4;k++)
            tran(j,k);
}
int las(int mac){
    int a[16]; a[0]=0;
    for(int i=1;i<=n;i++) a[i]=a[i-1]+((mac>>(i-1))&1);
    return a[n];
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(trans,0,sizeof(trans));
        memset(f,0,sizeof(f));
        memset(ans,0,sizeof(ans));
        //清空数组 
        scanf("%s%d",s,&m);
        n=strlen(s);
        for(int i=1;i<=n;i++)
            switch(s[i-1]){
                case 'A':q[i]=1;break;
                case 'C':q[i]=2;break;
                case 'G':q[i]=3;break;
                case 'T':q[i]=4;break;
            }//把字符转化成好处理的数字 
        pre();//预处理 
        bool id=1;//滚动 
        f[0][0]=1;//初始化(因为第一层id=1所以这里是f[1][0]=1) 
        for(int i=1;i<=m;i++){
            id=!id;
            for(int j=0;j<=(1<<n)-1;j++) f[!id][j]=0;//先清零！ 
            for(int j=0;j<=(1<<n)-1;j++)//枚举mac 
                for(int k=1;k<=4;k++)//枚举k 
                    f[!id][trans[j][k]]=(f[!id][trans[j][k]]+f[id][j])%mod;
        }
        for(int j=0;j<=(1<<n)-1;j++)//枚举mac 
            ans[las(j)]=(ans[las(j)]+f[!id][j])%mod;
        for(int i=0;i<=n;i++) printf("%d\n",ans[i]);
    }
}