HDU 1080 Human Gene Functions

最长公共子序列的变形

题目大意:给出两个基因序列,求这两个序列的最大相似度。

题目中的表格给出了两两脱氧核苷酸的相似度。

状态转移方程为:

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

注意边界的初始化。

 //#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; char s1[], s2[];
int dp[][]; int table[][] = {
, -, -, -, -,
-, , -, -, -,
-, -, , -, -,
-, -, -, , -,
-, -, -, -,
}; int max(int a, int b, int c)
{
return max(max(a, b), c);
} int f(char c)
{
if(c == 'A') return ;
if(c == 'C') return ;
if(c == 'G') return ;
if(c == 'T') return ;
if(c == '-') return ;
} int Similarity(char c1, char c2)
{ return table[f(c1)][f(c2)]; } int main(void)
{
#ifdef LOCAL
freopen("1080in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
int len1, len2, i, j;
dp[][] = ;
scanf("%d %s", &len1, s1+);
scanf("%d %s", &len2, s2+);
for(i = ; i <= len1; ++i)
dp[i][] = dp[i-][] + Similarity(s1[i], '-');
for(i = ; i <= len2; ++i)
dp[][i] = dp[][i-] + Similarity(s2[i], '-');
for(i = ; i <= len1; ++i)
for(j = ; j <= len2; ++j)
dp[i][j] = max(dp[i-][j]+Similarity(s1[i], '-'),
dp[i][j-]+Similarity(s2[j], '-'),
dp[i-][j-]+Similarity(s1[i], s2[j])); printf("%d\n", dp[len1][len2]);
}
return ;
}

代码君

上一篇:-bash: ./test.sh: /bin/bash^M: bad interpreter: No such file or directory


下一篇:简例 - robot case格式