HDU 1080 Human Gene Functions (DP) by kuangbin

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1080

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[110][110];
int Maxtri[5][5]=
{
{0,-3,-4,-2,-1},
{-3,5,-1,-2,-1},
{-4,-1,5,-3,-2},
{-2,-2,-3,5,-2},
{-1,-1,-2,-2,5}
};
int num1[110];
int num2[110];
int main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
int T;
int n,m;
char ch;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
getchar();
for(int i=1;i<=n;i++)
{
scanf("%c",&ch);
if(ch=='A') num1[i]=1;
else if(ch=='C') num1[i]=2;
else if(ch=='G') num1[i]=3;
else if(ch=='T') num1[i]=4;
}
scanf("%d",&m);
getchar();
for(int i=1;i<=m;i++)
{
scanf("%c",&ch);
if(ch=='A') num2[i]=1;
else if(ch=='C') num2[i]=2;
else if(ch=='G') num2[i]=3;
else if(ch=='T') num2[i]=4;
}
dp[0][0]=0;
for(int i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+Maxtri[num1[i]][0];
for(int i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+Maxtri[0][num2[i]];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=max(dp[i-1][j-1]+Maxtri[num1[i]][num2[j]],max(dp[i-1][j]+Maxtri[num1[i]][0],dp[i][j-1]+Maxtri[0][num2[j]]));
}
}
printf("%d\n",dp[n][m]);

}
}
原文地址:https://www.cnblogs.com/kuangbin/p/2262268.html