POJ1080 Human Gene Functions(LCS)

时间:2024-10-08 20:05:32

题目链接。

分析:

和 LCS 差不多。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map> using namespace std; const int maxn = ; int G[][] = {
{, -, -, -, -},
{-, , -, -, -},
{-, -, , -, -},
{-, -, -, , -},
{-, -, -, -, }
}; int dp[maxn][maxn]; void trans(char *s, int n) {
for(int i=; i<n; i++) {
switch(s[i]) {
case 'A': s[i] = ; break;
case 'C': s[i] = ; break;
case 'G': s[i] = ; break;
case 'T': s[i] = ; break;
case '-': s[i] = ; break;
}
}
} int main(){
int T, n, m;
// freopen("my.txt", "r", stdin);
char s1[maxn], s2[maxn]; scanf("%d", &T); while(T--) {
scanf("%d%s%d%s", &n, s1, &m, s2);
trans(s1, n); trans(s2, m); dp[][] = ;
for(int i=; i<=m; i++) dp[i][] = G[s2[i-]][] + dp[i-][]; for(int i=; i<=n; i++) dp[][i] = G[s1[i-]][] + dp[][i-]; for(int i=; i<=m; i++) {
for(int j=; j<=n; j++) {
int u = s2[i-], v = s1[j-]; dp[i][j] = dp[i-][j-] + G[u][v];
dp[i][j] = max(dp[i][j], dp[i-][j]+G[u][]);
dp[i][j] = max(dp[i][j], dp[i][j-]+G[v][]);
}
} printf("%d\n", dp[m][n]);
} return ;
}