首页 > 代码库 > ZOJ 1642 Match for Bonus (DP)
ZOJ 1642 Match for Bonus (DP)
题目链接
题意 : 给你两个字符串,两个字符串都有共同的字母,给你每个字母的值,规则是,找出两个字符串中的共同的一个字母,然后这个字母的值就可以加到自己的分数上,但是这步操作之后,这两个字母及其之前的字母都要删除掉,问你能够得到的最大的值是什么。
思路:最长公共子序列,加了一个权值。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string> 4 #include <string.h> 5 6 using namespace std; 7 8 int a[3101] ; 9 int dp[3101][3101] ; 10 int s ; 11 char ch ; 12 string sh1,sh2 ; 13 14 int main() 15 { 16 int n ; 17 while(cin >> n) 18 { 19 for(int i = 0 ; i < n ; i++) 20 { 21 cin >> ch >> s; 22 a[int(ch)] = s ; 23 } 24 cin >> sh1 >> sh2 ; 25 memset(dp,0,sizeof(dp)) ; 26 for(int i = 1 ; i <= sh1.size() ; i++) 27 for(int j = 1 ; j <= sh2.size() ; j++) 28 { 29 dp[i][j] = max(dp[i-1][j],dp[i][j-1]) ; 30 if(sh1[i-1] == sh2[j-1]) 31 dp[i][j] = max(dp[i][j],dp[i-1][j-1]+a[int(sh1[i-1])]) ; 32 } 33 printf("%d\n",dp[sh1.size()][sh2.size()]) ; 34 } 35 return 0; 36 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。