动态规划(DP),地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1080
#include <stdio.h>

 char tab[5] = {'A', 'C', 'G', 'T', '-'};

 int list[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,
};

int str1[105];
int str2[105];

int dp[105][105];

int find(char ch)
  {
int i;
for (i=0; i<5; i++)
 {
if (tab[i]==ch)
 {
break;
}
}
return i;
}

int max(int a, int b, int c)
  {

int m = a;
if (b>m)
 {
m = b;
}
if (c>m)
 {
m = c;
}
return m;
}

int lcs(int s1[], int len1, int s2[], int len2)
  {

int i, j;
for (i=0; i<=len1; i++)
 {
for (j=0; j<=len2; j++)
 {
if (i==0 && j==0)
 {
dp[i][j] = 0;
}
else if (i==0 && j!=0)
 {
dp[i][j] = dp[i][j-1] + list[4][s2[j-1]];
}
else if (i!=0 && j==0)
 {
dp[i][j] = dp[i-1][j] + list[s1[i-1]][4];
}
else
 {
dp[i][j] = max(dp[i-1][j-1]+list[s1[i-1]][s2[j-1]], dp[i][j-1]+list[4][s2[j-1]], dp[i-1][j]+list[s1[i-1]][4]);
}
}
}
return dp[i-1][j-1];
}

int main()
  {

int t, n1, n2;
int i;
char temp[105];
while (scanf("%d", &t) != EOF)
 {
while (t--)
 {
scanf("%d%s", &n1, &temp);
for (i=0; i<n1; i++)
 {
str1[i] = find(temp[i]);
}
scanf("%d%s", &n2, &temp);
for (i=0; i<n2; i++)
 {
str2[i] = find(temp[i]);
}
printf("%d\n", lcs(str1, n1, str2, n2));
}
}
return 0;
}

|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
24 | 25 | 26 | 27 | 28 | 29 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|