1027 dp.cpp

zoj 的1027题。 采用动态规划求解。

//zoj 1027 DP

/*

观察题目给出的一个最优解：
AGTGATG
-GTTA-G
将其从某一处切开，如果左边部分的分值不是最大，那么将其进行调整，使其分值变大，
则整个解分值变大，与已知的最优矛盾。所以左边部分的分值必是最大。同理，右边也是。
可见满足最优子结构的性质。考虑使用DP：

设两个DNA序列分别为s1，s2，长度分别为len1，len2，score为分值表。
f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j]，我们有：
1.s1取第i个字母，s2取“-”：f[i-1,j] + score[s1[i],'-']
2.s1取“-”，s2取第j个字母：f[i,j-1] + score['-',s2[j]]
3.s1取第i个字母，s2取第j个字母：f[i-1,j-1] + score[s1[i],s2[j]]
即f[i,j] =max(f[i-1,j] + score[s1[i],'-'], f[i,j-1] + score['-',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]);

然后考虑边界条件，这道题为i或j为0的情况。
当i=j=0时，即为f[0,0]，这是在计算f[1,1]时用到的，
根据f[1,1] = f[0,0] + score[s1[i], s2[j]]，明显有f[0,0] = 0。
当i=0时，即为f[0,1..len2]，有了f[0,0]，可以用f[0,j] = f[0,j-1] + table['-',s2[j]]来计算。
当j=0时，即为f[1..len1,0]，有了f[0,0]，可以用f[i,0] = f[i-1,0] + table[s1[i],'-']来计算。

至于计算顺序，只要保证计算f[i,j]的时候，使用到的f[i-1,j]，f[i,j-1]，f[i-1,j-1]都计算出来了就行了。
所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。

*/

#include "iostream"
#include "string"
using namespace std;

const int score[6][6]={
    {0,0,0,0,0,0},
    {0,5,-1,-2,-1,-3},
    {0,-1,5,-3,-2,-4},
    {0,-2,-3,5,-2,-2},
    {0,-1,-2,-2,5,-1},
    {0,-3,-4,-2,-1,0}
  };
  
int get(char c) {
   if(c == 'A')return 1;
   if(c == 'C')return 2;
   if(c == 'G')return 3;
   if(c == 'T')return 4;
   return 5;
   }

 int max3(int a,int b,int c) {
      if(a<b) a=b;
      if(a<c) return c;
      else return a;
      }
   
int main() {
   int f[101][101],s1[101],s2[101],t,len1,len2,i,j;
   string st1,st2;
   cin>>t;
   while(t--) {
     cin>>len1>>st1>>len2>>st2;
     for(i=1;i<=len1;i++)
     s1[i]=get(st1[i-1]);
     for(i=1;i<=len2;i++)
     s2[i]=get(st2[i-1]);
     
     //边界条件
     f[0][0]=0;
     for(i=1;i<=len1;i++)
     f[i][0]=f[i-1][0]+score[s1[i]][5];
     for(j=1;j<=len2;j++)
     f[0][j]=f[0][j-1]+score[5][s2[j]];
     
     for(i=1;i<=len1;i++)
       for(j=1;j<=len2;j++)
         f[i][j]=max3(f[i-1][j-1]+score[s1[i]][s2[j]],
                      f[i-1][j]+score[s1[i]][5],
                      f[i][j-1]+score[5][s2[j]]);
                      
     cout<<f[len1][len2]<<endl;
    }
    return 0;
  }