## ZOJ 1642 Match for Bonus（dp）

2018年01月19日 ⁄ 综合 ⁄ 共 1543字 ⁄ 字号 评论关闭

Match for Bonus

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Roy played a game with his roommates the other day.

His roommates wrote 2 strings of characters, and gave each character a bonus value. When Roy pinned the positions of one common character in the 2 strings, the bonus value of that character would be added to Roy's score. However at the mean time, the 2 characters
and those before them in the strings would be erased.

Roy now needs your help, because he wants to know the maximum score he can get.

Input

There are several test cases.

For each test case, the first line contains an integer N.

The following N lines describe a list of N characters and their bonus values.

Then the following 2 lines give the 2 strings.

Output

For each test case, output in one line the best score Roy can get.

Sample Input

3
a 1
b 1
c 1
abc
bca
3
a 1
b 10
c 100
abc
cab

Sample Output

2
100

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL;

map<char, int> mp;
string s1, s2;
const int N = 2010;
int dp[N][N];
int fun()
{
memset(dp, 0, sizeof(dp));
int len1 = s1.length(), len2 = s2.length();
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + mp[s1[i-1]];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[len1][len2];
}
int main()
{
int n, val;
char ch;
while(cin >> n) {
mp.clear();
for(int i = 0; i < n; i++) {
cin >> ch >> val;
mp[ch] = val;
}
cin >> s1 >> s2;
cout << fun() << endl;
}
return 0;
}```