hdu4899 Hero meet devil

タイトルリンク
に言及
4種類の文字((A,C,G,T))のみを含む長さ文字列(T)を指定します.(S)の長さが(m)、質問(S)および(T)の(lcs)が(0,1,2...|T|)の場合、それぞれいくつの場合がありますか.(|T| <= 15,m <= 1000\)
構想
考え(dp)スリーブ(dp)(dpはネストできますか?)既知のSの場合、(lcs)を(f[i][j])で表し、(S)が(i)位置に、(T)が(j)位置に、最も長い共通サブシーケンスの長さをどのように求めるかを考慮します.それは[dp[i][j]=max(dp[i-1][j],dp[i][j-1])\if(S[i]==T[j])\dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)]設計状態を(f[i][t][t_t_0][t_1][t_1][t_2]…[t_n])で(S)が(i)位置に着いたことを表し、dp[i][0],dp[i][1],dp[i][2]...dp[i][n])でそれぞれ、t_n)のシナリオ数.そして時間も空間も爆発することに気づきました.したがって,状圧を考慮すると,(lcs)を求める式から,(dp[i][j])はせいぜい(dp[i][j-1])より大きいだけであることが分かるので,f配列の後ろの数字を差分するだけで,状圧が可能な状態になる.そして接頭辞とすぐにこの配列を復元することができます.だから(f[i][j])で(S)が(i)番目の位置に着いたことを表し、(dp)配列は(j)という状態のシナリオ数である.遷移はまず(g)配列を前処理し,(g[i][k])は(i)という状態を表し,次の位置は(k)というアルファベットで,遷移する状態を表す.この前処理は実は難しくない.まずiという状態を元に戻すだけです.それから、その方法を求めてください.最後にまた転化すればいいです.そして(f)配列の遷移であり、(g)配列だけが要求されたので、(f)配列の方が扱いやすい.[f[i][g[j][k]+=f[i-1][j]]複雑度は(O(m 2^{|T|}))
コード#コード#

/*
* @Author: wxyww
* @Date:   2019-01-20 10:33:34
* @Last Modified time: 2019-01-20 11:40:43
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 1<<15,mod = 1e9 + 7;
ll read() {
   ll x=0,f=1;char c=getchar();
   while(c'9') {
      if(c=='-') f=-1;
      c=getchar();
   }
   while(c>='0'&&c<='9') {
      x=x*10+c-'0';
      c=getchar();
   }
   return x*f;
}
char s[20];
int f[1005][N];
int n,tot,ss[20],tmp[2][20],sta[N][4];
void pre(int x) {
   for(int i = 1;i <= n;++i) {
      tmp[0][i] = (x >> (n - i) & 1) + tmp[0][i - 1];
   }
   for(int k = 0;k <= 3;++k) {
      memset(tmp[1],0,sizeof(tmp[1]));
      for(int i = 1;i <= n;++i) {
         tmp[1][i] = max(tmp[0][i],tmp[1][i - 1]);
         if(ss[i] == k)
            tmp[1][i] = max(tmp[1][i],tmp[0][i - 1] + 1);
      }
      int z = 0;
      for(int i = 1;i <= n;++i)
         z = z << 1 | (tmp[1][i] - tmp[1][i - 1]);
      sta[x][k] = z;
   }
}
int ans[N];
int calc(int x){
   int re = 0;
   while(x) {
      re += x & 1;
      x >>= 1;
   }
   return re;
}
int main() {
   int T = read();   
   while(T--) {
      memset(f,0,sizeof(f));

      scanf("%s",s + 1);
      n = strlen(s + 1);
      int m = read();
      for(int i = 1;i <= n;++i) {
         if(s[i] == 'A') ss[i] = 0;
         else if(s[i] == 'C') ss[i] = 1;
         else if(s[i] == 'G') ss[i] = 2;
         else ss[i] = 3;
      }
      tot = (1 << n) - 1;
      f[0][0] = 1;
      for(int i = 0;i <= tot;++i) pre(i);
      for(int i = 1;i <= m;++i)
         for(int j = 0;j <= tot;++j)
            for(int k = 0;k < 4;++k)
               f[i][sta[j][k]] += f[i - 1][j],f[i][sta[j][k]] %= mod;
      memset(ans,0,sizeof(ans));
      for(int i = 0;i <= tot;++i) {
         int z = calc(i);
         ans[z] += f[m][i],ans[z] %= mod;
      }
      for(int i = 0;i <= n;++i) {
         printf("%d
",ans[i]);
      }
   }

   return 0;
}
/*
2
GTC
10
GTC
10
*/