POJ 1080 Human Gene Functions（字符串匹配得分，dp）

题目链接；
POJ 1080 Human Gene Functions
题意：
给出两个长度不超过$100$，且只含字母$A,G,C,T$的字符串，需要将两个字符串匹配得分，每个字母可以和空格对应，得分规则如下：

求最大得分。
分析:
这道题和之前做过的UVAL ive 6697 Homework Evaluation很类(yi)似(yang)。

$$dp[i][j][0]表示第二个串的第j个字母和第一个串的第i个字母匹配时的最大得分$$
$$dp[i][j][1]表示第二个串的的j个字母插在第一个串的第i个字母之前的最大得分$$
然后枚举第二个串的第 $j-1$个字母匹配的位置进行状态转移。
需要注意边界情况，比如第二个串的第一个字母和第一个串的第i个字母匹配时 $dp[i][1][0]$的情况，还有将第二个串的后面字母都和第一个串最后面的空格匹配的情况，相当于将第二个串的字母插在第一个串的第 $len_1+1$个字母前面，而实际上这个位置是没有字母的。还有最后枚举答案时，别忘了第一个串还有没匹配字母的情况。

#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
const int MAX_N = 110;
const int inf = 0x3f3f3f3f;char s1[MAX_N], s2[MAX_N];
int dp[MAX_N][MAX_N][2], sum[MAX_N];inline int work1(char c)
{if (c == 'A') return -3;if (c == 'C') return -4;if (c == 'G') return -2;if (c == 'T') return -1;    
}inline int work2(char c1, char c2)
{if (c1 == c2) return 5;if (c1 > c2) swap(c1, c2);if (c1 == 'A') {if (c2 == 'C') return -1;if (c2 == 'G') return -2;if (c2 == 'T') return -1;} else if (c1 == 'C') {if (c2 == 'G') return -3;if (c2 == 'T') return -2;} else return -2;
}int main()
{int T, len1, len2;scanf("%d", &T);while (T--) {scanf("%d%s", &len1, s1 + 1);scanf("%d%s", &len2, s2 + 1);for(int i = 0; i < MAX_N; ++i) {for(int j = 0; j < MAX_N; ++j) {if (i == 0 || j == 0) dp[i][j][1] = dp[i][j][0] = 0;else dp[i][j][0] = dp[i][j][1] = -inf;}   }sum[0] = 0;for(int i = 1; i <= len1; ++i) {sum[i] = sum[i - 1] + work1(s1[i]);}for (int i = 1; i <= len1 + 1; ++i) {dp[i][1][0] = sum[i - 1] + work2(s1[i], s2[1]);dp[i][1][1] = sum[i - 1] + work1(s2[1]);for(int j = 2; j <= len2; ++j) {for (int k = 1; k < i; ++k) {dp[i][j][0] = max(dp[i][j][0], dp[k][j - 1][0] + sum[i - 1] - sum[k]);dp[i][j][0] = max(dp[i][j][0], dp[k][j - 1][1] + sum[i - 1] - sum[k - 1]);dp[i][j][1] = max(dp[i][j][1], dp[k][j - 1][0] + sum[i - 1] - sum[k]);dp[i][j][1] = max(dp[i][j][1], dp[k][j - 1][1] + sum[i - 1] - sum[k - 1]);}dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][1]);if (i <= len1) dp[i][j][0] += work2(s1[i], s2[j]);else dp[i][j][0] += work1(s2[j]);dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1]);dp[i][j][1] += work1(s2[j]);// printf("dp[%d][%d][0] = %d dp[%d][%d][1] = %d\n", i, j, dp[i][j][0], i, j, dp[i][j][1]);}}int ans = -inf;for(int i = 1; i <= len1; ++i) {ans = max(ans, dp[i][len2][0] + sum[len1] - sum[i]);ans = max(ans, dp[i][len2][1] + sum[len1] - sum[i - 1]);}ans = max(ans, dp[len1 + 1][len2][1]);printf("%d\n", ans);}return 0;
}