hdu 1080 dp Human Gene Functions

本文主要是介绍hdu 1080 dp Human Gene Functions，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分三种情况考虑。

dp[i][j]=max(dp[i-1][j-1]+a[s1[i]][s2[j]],max(dp[i-1][j]+a[s1[i]][4],dp[i][j-1]+a[s2[j]][4]));

#include <iostream>
using namespace std;
int max(int a,int b)
{return a>b?a:b;
}int main()
{int t;int n1,n2;int s1[105],s2[105];char ch;int dp[105][105];int a[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 ",&n1);for(int i=1;i<=n1;i++){scanf("%c",&ch);if(ch=='A') s1[i]=0;if(ch=='C') s1[i]=1;if(ch=='G') s1[i]=2;if(ch=='T') s1[i]=3;}scanf("%d ",&n2);for(int i=1;i<=n2;i++){scanf("%c",&ch);if(ch=='A') s2[i]=0;if(ch=='C') s2[i]=1;if(ch=='G') s2[i]=2;if(ch=='T') s2[i]=3;}dp[0][0]=0;for(int i=1;i<=n1;i++)dp[i][0]=dp[i-1][0]+a[s1[i]][4];for(int i=1;i<=n2;i++)dp[0][i]=dp[0][i-1]+a[s2[i]][4];for(int i=1;i<=n1;i++)for(int j=1;j<=n2;j++)dp[i][j]=max(dp[i-1][j-1]+a[s1[i]][s2[j]],max(dp[i-1][j]+a[s1[i]][4],dp[i][j-1]+a[s2[j]][4]));printf("%d\n",dp[n1][n2]);}return 0;
}

这篇关于hdu 1080 dp Human Gene Functions的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---