首页 > 代码库 > ZOJ 1642

ZOJ 1642

2024-07-28 17:30:15   218人阅读

题意：有两个字符串，每个串由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);    }}
View Code

 

ZOJ 1642


联系
我们