河南省第十二届省赛 B题 DNA序列---同源问题（简单DP）

题目链接：DNA序列—同源问题 输入描述:

输入有多组测试数据（不超过20组），每组数据格式如下： 第一行： a b c d (4个整数 1 ≤ a , b, c ,d ≤ 20） 第二行： s ( | s| ≤ 300 ) 第三行： t ( |t| ≤ 300 )

输出描述:

对每组测试数据，输出占一行, 将序列s演变为序列t的最高得分f.

样例输入:

1 1 2 2 CTA CTGAA 1 1 1 1 CDDAA CAA

样例输出:

-1 1

这个题目的题目描述很简单，就是把字符串 s 演变成 t 的最大得分。其实也就是一个字符串匹配。 可以细想一下，如果让字符串 s 的第 0 个字符（不是下标为0），准确的说就是让一个空字符取匹配字符串 t 中的任何一个字符，都需要让字符串 s 的第 0 个字符加上后续的字符，那么得分就是 -c * i，对应代码中的一个dp数组初始化过程。 如果让字符串 t 的第 0 个字符取匹配字符串 s 中的每一个字符， s 中的字符相当于缺失，所以得分为 -d * i，对应另一个dp数组的初始化过程。

注意：为什么不能反过来？如果让 t 中的 0 个字符匹配 s ，为什么不能让 t 增加？ 因为我们要操作的是字符串 s ，也就是让字符串 s 演变成 t，s是起始串，可变；但t是目标串，不可变。 dp[ i ] [ j ]表示的是字符串 s 中的前 i 个字符和 t 中前 j 个字符匹配的最大得分。 剩下的就是状态转移方程了。方程如下：

if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + a; } else { dp[i][j] = dp[i - 1][j - 1] - b; dp[i][j] = max(dp[i][j], dp[i][j - 1] - c); dp[i][j] = max(dp[i][j], dp[i - 1][j] - d); }

循环变量 i ，我是从1开始的，所以 i - 1和 j - 1对应是 s 和 t 中的第 i 和第 j 个字符。 如果字符串中 s [ i - 1 ] == t [ j - 1 ]，也就是s中的第 i - 1个字符和 t 中第 j - 1个字符一样，就可以直接匹配了。因为题目要求 a,b,c,d 都大于 0，也就是说，只有匹配得正分，其余操作都是负分。这样的话，dp[ i ][ j ]就应该是 s 中前 i -1 个字符和 t 中前 j-1个字符匹配的最大得分加上本次匹配的得分 a 如果无法完成匹配，有三种可能。 1、直接替换，所以就成了 s 中前 i -1 个字符和 t 中前 j-1个字符匹配的最大得分减去替换所消耗的得分，即

dp[i][j] = dp[i - 1][j - 1] - b;

2、在 s 中增添一个可以和 t 的第 j - 1 个字符成功匹配的字符，这样就相当与 t 的第 j - 1个字符和新字符匹配了，得分就是 s 的前 i 个字符和 t 的第 j - 1个字符匹配的最大得分减去增添消耗的得分，即

dp[i][j] = dp[i][j - 1] - c;

3、在 t 字符串 s 的第 i 个字符显示为缺失，也就成为了 s 的第 i 个字符丢失，前 i - 1个字符和 t 的前 j 个字符匹配，得分是前 i - 1个字符和 t 的前 j 个字符匹配的最大得分减去缺失丢失的分数，即

dp[i][j] = dp[i - 1][j] - d;

从这三种情况中，选取一个得分最大的值作为dp[i][j]的值即可。 最后输出 dp[ s.length() ] [ t.length() ]即可。

#include<bits/stdc++.h> using namespace std; int a, b, c, d; string s, t; int dp[330][330]; int main() { while (cin >> a >> b >> c >> d) { //匹配得分为 a，替换为 -b，增加为 -c，丢失为 -d cin >> s >> t; memset(dp, 0, sizeof dp); int len1 = s.length(); int len2 = t.length(); for (int i = 1; i <= len1; i++) { dp[i][0] = -1 * d*i; } for (int i = 1; i <= len2; i++) { dp[0][i] = i * c*-1; } for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + a; } else { dp[i][j] = dp[i - 1][j - 1] - b; dp[i][j] = max(dp[i][j], dp[i][j - 1] - c); dp[i][j] = max(dp[i][j], dp[i - 1][j] - d); } } } cout << dp[len1][len2] << endl; } return 0; }