uvalive 6697 - Homework Evaluation - dp

本文主要是介绍uvalive 6697 - Homework Evaluation - dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出两个字符串，用第二个字符串去匹配第一个字符串，可以对第二个字符串进行删除或插入操作，一位匹配成功得8分失败-5分，如果插入或删除，对于连续插入或删除m个数减(4+m * 3)分。求最终得分的最大值。

用dp[i][j]表示第二个串的第i位和第一个串的第j位匹配得分的最大值，dp[i][j]可以是dp[i - 1][j - 1]继续匹配也可能是dp[i - 1][k]通过插入一段串得到或者dp[k][j - 1]通过在第二个串删除一段得到。最后扫描第二串匹配完的结果找最大值。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[200][200];
char s[150], t[150];
int main() {int tt, n, m, i, j, k;scanf("%d", &tt);while(tt--) {scanf("%s%s", s + 1, t + 1);n = strlen(s + 1);m = strlen(t + 1);for(i = 1; i <= m; i++) {dp[i][0] = -4 - 3 * i;for(j = 1; j <= n; j++) {dp[i][j] = dp[i - 1][j - 1];for(k = 0; k < j - 1; k++) {dp[i][j] = max(dp[i][j], dp[i - 1][k] - 4 - 3 * (j - k - 1));}for(k = 0; k < i - 1; k++) {dp[i][j] = max(dp[i][j], dp[k][j - 1] - 4 - 3 * (i - k - 1));}if(s[j] == t[i])dp[i][j] += 8;else dp[i][j] -= 5;}}int ans = dp[m][1];for(i = 0; i <= n; i++)ans = max(ans, dp[m][i]);printf("%d\n", ans);}return 0;
}

这篇关于uvalive 6697 - Homework Evaluation - dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---