解题报告_ZOJ1642.pptVIP

解题报告：ZOJ 1642 报告人：__张海峰__ 全代码如下 #includeiostream #includecstdio #includecstring using namespace std; #define MAXN 2005 char s; char s1[MAXN],s2[MAXN]; int dp[MAXN][MAXN]; int S[500]; int max(int a,int b) { if(ab) return a; else return b; } int main() { int n; int a; int ans; while( scanf(%d,n) != EOF ) { memset(S,0,sizeof(S)); int i,j; for(i=0;in;i++) { getchar(); scanf(%c%d,s,a); S[s] = a; } scanf(%s%s,s1,s2); memset(dp,0,sizeof(dp) ); ans= 0; for(i=0;s1[i];i++) { for( j=0;s2[j];j++) { dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]); if(s1[i]==s2[j])dp[i+1][j+1]=max(dp[i][j]+S[s1[i]] ,dp[i+1][j+1]); if(dp[i+1][j+1]ans )ans = dp[i+1][j+1]; } } printf(%d\n,ans); } return 0; } * 信息学院信息技术教研室 程序设计方法及在线实践 * * 题目来源:?ZOJ Monthly, September 2003 题号： ZOJ 1642 题目描述： 有一天夜里，小明和他的室友玩一个字符串匹配游戏。 游戏规则是：由他室友随兴写两个字符串s1,s2。并且由他室友给字符串中每一个字符规定一个分值。小明可以通过找出一个匹配的子串，获得该匹配子串上所有字符的分数和。小明想获得最高分，但是他又不懂其中奥秘，所以他想请你帮忙求解。 输入描述： 该输入有多组测试数据。每组测试数据首先是一个整数N，接下来是N行，每行一个字符 C和赋予它的分数 V。 最后两行给出字符串s1,s2。测试数据直到文件尾。 输出描述： 对于每组测试数据，输出小明能获得的最大分数。 样例输出： 2 100 样例输入： 3 a 1 b 1 c 1 abc bca 3 a 1 b 10 c 100 abc cab 分析：这是一道DP的经典类型的变题，其实就是用DP找到权值最大的公共子串。 可以用一个二维数组记录，ans作为最小的权值。 DP核心代码 ans= 0; for(i=0;s1[i];i++) { for( j=0;s2[j];j++) { dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]); if(s1[i]==s2[j])dp[i+1][j+1]=max(dp[i][j]+S[s1[i]],dp[i+1][j+1; if(dp[i+1][j+1]ans )ans = dp[i+1][j+1]; } } *