ACM/ICPC 之 DP-基因相似度(POJ1080-ZOJ1027)

题意：两端基因片段，各有明确的碱基序列，现有一个碱基匹配的相似度数组，设计程序使得该相似度最大。

---

 //POJ1080-ZOJ1027

 //题解：将s1碱基和s2碱基看做等长，添加一个碱基为'-'，即每次都将上下碱基相互匹配后再和'-'匹配，找到最优解即可

 //即分为三种状态：

 //    1.s1[i]和s2[j]匹配

 //    2.s1[i]和 '-' 匹配

 //    3. '-' 和s2[j]匹配

 #include <iostream>

 #include <cstdio>

 #include <map>

 using namespace std;

 #define MAX 105

 #define max(x,y) ((x)>(y)?(x):(y))

 char s1[MAX], s2[MAX];

 int len1, len2;

 int dp[MAX][MAX];    //dp[i][j]：s1基因的前i个碱基和s2基因的前j个碱基中的最优匹配解

 map<char, int> gene;    //碱基和adjust下标一一映射

 int adjust[][] = {    {,-,-,-,-},

                         {-,,-,-,-},

                         {-,-,,-,-},

                         {-,-,-,,-},

                         {-,-,-,-,}};

 int main()

 {

     int T;

     scanf("%d", &T);

     gene['A'] = ; gene['C'] = ;

     gene['G'] = ; gene['T'] = ;

     gene['-'] = ;

     while (T--)

     {

         scanf("%d %s", &len1, s1);

         scanf("%d %s", &len2, s2);

         memset(dp, , sizeof(dp));

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

             dp[i][] = dp[i-][] + adjust[gene[s1[i - ]]][gene['-']];    //上碱基各碱基仅匹配'-'时

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

             dp[][j] = dp[][j-] + adjust[gene['-']][gene[s2[j - ]]];    //下碱基各碱基仅匹配'-'时

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

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

             {

                 dp[i][j] = max(dp[i][j - ] + adjust[gene['-']][gene[s2[j - ]]],

                     dp[i - ][j] + adjust[gene[s1[i - ]]][gene['-']]);        //上下碱基各匹配'-'时

                 dp[i][j] = max(dp[i][j], dp[i - ][j - ] + adjust[gene[s1[i - ]]][gene[s2[j - ]]]);    //上下碱基相互配对时

             }

         printf("%d\n", dp[len1][len2]);

     }

     return ;

 }