HDU 4899 Hero meet devil-白红宇

HDU 4899 Hero meet devil

阅读量：4963 次

发布时间：2019-06-12

本文共 2254 字，大约阅读时间需要 7 分钟。

题意：一段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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing 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\n", prt[i]); } return 0;}