基因配对 给出俩基因链和配对的值 求配对值得最大值 简单dp
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxa = ;
const int mina = -;
char str1[maxa], str2[maxa];
int num[][] = {
, -, -, -, -,
-, , -, -, -,
-, -, , -, -,
-, -, -, , -,
-, -, -, -,-
};
int a1[maxa], a2[maxa];
int dp[maxa][maxa];
int main(){
//freopen("in.cpp", "r", stdin);
int t, n1, n2;
scanf("%d", &t);
while(t--){
str1[] = ;
str2[] = ;
scanf("%d%s", &n1, str1+);
scanf("%d%s", &n2, str2+);//printf("*"); for(int i = ; i <= n1; i++){
// printf("%c", str1[i]);
if(str1[i] == 'A')
str1[i] = ;
else if(str1[i] == 'C')
str1[i] = ;
else if(str1[i] == 'G')
str1[i] = ;
else str1[i] = ;
}
for(int i = ; i <= n2; i++){//printf("%d\n", i);
if(str2[i] == 'A')
str2[i] = ;
else if(str2[i] == 'C')
str2[i] = ;
else if(str2[i] == 'G')
str2[i] = ;
else str2[i] = ;
}//printf("*");
for(int i = ; i <= n1; i++){
if(i == )
a1[i] = num[str1[i]][];
else a1[i] = num[str1[i]][] + a1[i-];
}
for(int i = ; i <= n2; i++){
if(i == )
a2[i] = num[str2[i]][];
else a2[i] = num[str2[i]][] + a2[i-];
}
/*for(int i =0; i <= n1; i++){
printf("%d ", a1[i]);
}puts("");*/
for(int i = ;i <= n1; i++){
for(int k = ; k <= n2; k++){
dp[i][k] = mina;
}
}
for(int i = ; i <= n2; i++){
if(i == )
dp[][i] = num[str1[]][str2[i]];
else
dp[][i] = num[str1[]][str2[i]] + a2[i-]-a2[];
}
for(int i = ; i <= n1; i++){
dp[i][] = a1[i] - a1[];
for(int k = ; k <= n2; k++){
dp[i][k] = max(dp[i][k], dp[i-][k]+ num[str1[i]][]);
for(int j = ; j < k; j++){
dp[i][k] = max(dp[i][k],dp[i-][j] + num[str1[i]][str2[k]] + a2[k-] - a2[j]);
}
}
}
/*for(int i = 1; i <= n1; i++){
printf("*%d ", num[str1[i]][str2[1]]+a1[i-1]-a1[0]);
}puts("");;
for(int i = 0; i <= n1; i++){
for(int k = 0; k <= n2; k++){
printf("%d%d %d ",str1[i], str2[k], dp[i][k]);
}puts("");
}*/
int ans = mina;
for(int i = ; i <= n2; i++){
ans = max(ans, dp[n1][i] + a2[n2] - a2[i]);
// printf("%d ", dp[n1][i] + a2[n2] - a2[i]);
}//puts("");
for(int i = ; i <= n1; i++){
ans = max(ans, dp[i][n2]+a1[n1] - a1[i]);
//printf("%d ", dp[i][n2]+a1[n1] - a1[i]);
}//puts("");
printf("%d\n", ans);
} }