hdu 1080 Human Gene Functions --- LCS问题变形 - c++编程基础

题意：

两个字符串包含 A T C G - 五种字符两两之间对应一个数值

给两个字符串可以向其中添加一定的- 要使两字符串对应分值和最大求该值

很好的LCS变形。。

dp[i][j]表示s1前i位和s2前j位所能构成的最大值

那么如何递推呢根据题意

比较到 i j 位时此时可以有三种情况

1、s1[i] 对应 -

2、s2[j] 对应 -

3、s1[i] 对应 s2[j]

注意一下字符对应到分值的细节就是个简单的问题了

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #define inf 0x3f3f3f3f #define ll __int64 using namespace std; map
          
            mp; int dp[105][105];//dp[i][j]表示s1前i位和s2前j位所能构成的最大值 char s1[105],s2[105]; int max3(int a,int b,int c) { if(a>b) { if(a>c) return a; return c; } else { if(b>c) return b; return c; } } int main() { int l1,l2,t,i,j,tmp1,tmp2,tmp3; mp['A']=0; mp['C']=1; mp['G']=2; mp['T']=3; mp['-']=4; int sco[5][5]={ {5,-1,-2,-1,-3}, {-1,5,-3,-2,-4}, {-2,-3,5,-2,-2}, {-1,-2,-2,5,-1}, {-3,-4,-2,-1,0}}; scanf("%d",&t); while(t--) { scanf("%d%s%d%s",&l1,s1,&l2,s2); //初始化 dp[0][0]=0; for(i=1;i<=l1;i++) dp[i][0]=dp[i-1][0]+sco[mp[s1[i-1]]][4]; for(i=1;i<=l2;i++) dp[0][i]=dp[0][i-1]+sco[4][mp[s2[i-1]]]; for(i=1;i<=l1;i++) { for(j=1;j<=l2;j++) { tmp1=dp[i-1][j]+sco[mp[s1[i-1]]][4]; tmp2=dp[i][j-1]+sco[4][mp[s2[j-1]]]; tmp3=dp[i-1][j-1]+sco[mp[s1[i-1]]][mp[s2[j-1]]]; dp[i][j]=max3(tmp1,tmp2,tmp3); } } printf("%d\n",dp[l1][l2]); } return 0; }