Luogu P1140 相似基因 【dp】By cellur925

最近博客更不起来...然后又（照例）犯鼻炎了唉难受。

题目传送门

我们首先可以预处理碱基间的权值表。然后讲读入的碱基转化为数字，就变成了“数字匹配使权值最大”的问题。我们显然可以用动态规划解决。

两个序列配对上的dp状态设计相似，以前做过一道编辑距离也是类似配对的问题。

设f[i][j]表示第一个基因当前位置到了第i个碱基，第二个基因当前位置到了第j个碱基所能得到的最大相似度。

转移：lena*lenb 而且和状态也没有什么地方可以优化了。

决策：我们可以在每一次转移的时候有3种决策：

　　　　　　　　　　　　　　　　　　　　　　A串留空/B串留空/AB恰好匹配

预处理：当一个串与另一个（完全）空的串匹配时显然只有一种情况，所有状态开始由他转移而来。

     for(int i=;i<=lenb;i++) f[][i]=f[][i-]+w[b[i]][];

     for(int i=;i<=lena;i++) f[i][]=f[i-][]+w[a[i]][];

然鹅...在这被坑了，由于有负数的权值，还要再赋一个负无穷的初值，以及f[0][0]=0!!!

Code

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int lena,lenb;

 int w[][];

 int a[],b[],f[][];

 char A[],B[];

 void init()

 {

     for(int i=;i<=;i++) w[i][i]=;

     w[][]=w[][]=w[][]=w[][]=w[][]=w[][]=-;

     w[][]=w[][]=w[][]=w[][]=-;

     w[][]=w[][]=w[][]=w[][]=w[][]=w[][]=w[][]=w[][]=-;

     w[][]=w[][]=-;

 }

 int main()

 {

     init();

     /*for(int i=1;i<=5;i++)

     {

         for(int j=1;j<=5;j++)

             printf("%d ",w[i][j]);

         printf("\n");

     }*/

     scanf("%d",&lena);

     scanf("%s",A+);

     for(int i=;i<=lena;i++)

     {

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

         if(A[i]=='C') a[i]=;

         if(A[i]=='G') a[i]=;

         if(A[i]=='T') a[i]=;

     }

     scanf("%d",&lenb);

     scanf("%s",B+);

     for(int i=;i<=lenb;i++)

     {

         if(B[i]=='A') b[i]=;

         if(B[i]=='C') b[i]=;

         if(B[i]=='G') b[i]=;

         if(B[i]=='T') b[i]=;

     }

     memset(f,,sizeof(f));

     f[][]=;

     for(int i=;i<=lenb;i++) f[][i]=f[][i-]+w[b[i]][];

  /*    for(int i=1;i<=lenb;i++)

      printf("%d ",f[0][i]);*/

     for(int i=;i<=lena;i++) f[i][]=f[i-][]+w[a[i]][];

     for(int i=;i<=lena;i++)

      for(int j=;j<=lenb;j++)

       {

             f[i][j]=max(f[i][j],f[i-][j]+w[a[i]][]);

             f[i][j]=max(f[i][j],f[i][j-]+w[b[j]][]);

             f[i][j]=max(f[i][j],f[i-][j-]+w[a[i]][b[j]]);

       }

     printf("%d",f[lena][lenb]);

     return ;

 }