题意 : 题目链接
分析 :
可以观察到给出的配对代价表中对角线部分是正数
其余的都是负数，也就是说让相同字母的匹配的越多越好
即找出 LCS 但是这里 DP 的过程需要记录一下代价
有关 LCS 的一篇博客 ==> Click here
如果不是计算长度而是计算配对的价值，那么初始化的时候
记得将每一个串的字母作为结尾与空串配对的价值初始化一下
即 dp[i][0] 与 dp[0][i]
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 10; int cost[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, -INF} }; char str1[maxn], str2[maxn]; map<char, int> mp; int dp[maxn][maxn]; int main(void) { mp['A'] = 0, mp['C'] = 1, mp['G'] = 2, mp['T'] = 3, mp['-'] = 4; memset(dp, -INF, sizeof(dp)); int N, M; scanf("%d", &N); for(int i=1; i<=N; i++) scanf(" %c", &str1[i]); scanf("%d", &M); for(int i=1; i<=M; i++) scanf(" %c", &str2[i]); dp[0][0] = 0; for(int i=1; i<=N; i++) dp[i][0] = dp[i-1][0] + cost[mp[str1[i]]][4]; for(int i=1; i<=M; i++) dp[0][i] = dp[0][i-1] + cost[4][mp[str2[i]]]; /* 对于上面这两个 for 循环的初始化，实际上就是对每一个串到 i 为结尾与一个空串 做匹配的结果，即到 i 为止，整个串与空碱基做匹配的代价，这个初始化是有必要的 举个例子 1 A 3 TGC 没有这个初始化的话 错误答案就是 -7 对应如下情况 --- TGC 实际最优的情况是 -4 对应如下情况 --A TGC 因为没有这个初始化，dp[1][j] 的情况不能从 dp[i-1][j-1] 转移而来 即让第一个串的第 1 字符与当前第二个串的第 j 个字符做匹配的代价 对于LCS这种DP的变体，记得这个初始化！ */ for(int i=1; i<=N; i++){ for(int j=1; j<=M; j++){ dp[i][j] = max(dp[i][j], dp[i-1][j-1] + cost[mp[str1[i]]][mp[str2[j]]]); dp[i][j] = max(dp[i][j], dp[i-1][j] + cost[mp[str1[i]]][4]); dp[i][j] = max(dp[i][j], dp[i][j-1] + cost[4][mp[str2[j]]]); } } // for(int i=1; i<=N; i++){ // for(int j=1; j<=M; j++){ // printf("%d ", dp[i][j]); // }puts(""); // } return !printf("%d ", dp[N][M]);; }