题意：有两个字符串，每个串由n个字符组成，每个字符有一个价值，Roy每次指定串2中的一个字符，他的得分增加的值为这个字符的价值，然后把两个串中这个字符前面的那部分（包括这个字符）删掉，重复进行这样的操作，求Roy最多能得多少分。
dp[i][k] 存的前str1的前i个和str2的前k个能取得最大值，接下来就不用说啥了，dp
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int maxa = 2000; int dp[maxa][maxa]; int value_char[500]; char str1[maxa], str2[maxa]; int main(){ int n; while(scanf("%d", &n)!=EOF){ for(int i = 0; i < n; i++){ char c; int d; scanf("\n%c %d", &c, &d); value_char[c] = d; } memset(dp, 0, sizeof(dp)); scanf("%s%s", str1, str2); int maxu = 0; for(int i = 0; str1[i]; i++){ int maxn = 0; for(int k = 0; str2[k]; k++){ if(str2[k] == str1[i]){ dp[i][k] = max(maxn + value_char[str1[i]], dp[i][k]); //printf("%d %d\n", i, k); //dp[i+1][k] = dp[i][k]; maxu = max(maxu, dp[i][k]); } maxn = max(maxn, dp[i][k]); } for(int k = 0; str2[k]; k++){ dp[i+1][k] = dp[i][k]; } } printf("%d\n", maxu); } }
原文：http://www.cnblogs.com/icodefive/p/4044131.html
