首页 > 代码库 > ZOJ 1642
ZOJ 1642
题意:有两个字符串,每个串由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); }}
ZOJ 1642
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。