zoj 1642 Match for Bonus（动态规划）-白红宇

zoj 1642 Match for Bonus（动态规划）

阅读量：7021 次

发布时间：2019-06-28

本文共 1744 字，大约阅读时间需要 5 分钟。

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

a 1

b 1

c 1

abc

bca

a 1

b 10

c 100

abc

cab

Sample Output

100

度娘的思路：本题的算法思想与LCS问题类似。设输入的2个字符串s1[0...n]和s2[0...m]，另f(i,j)表示子串s1[0...i]和s2[0...j]对应的最大得分，则有DP递推式

f(i,j)=max{f(i-1,j-1)+(x[i]==y[j])?v(x[i]):0，f(i,j-1)，f(i-1,j)}，（v(c)表示字符c的分值），所以最大得分便是f(n,m)。

我呢，各种犯错，记录下

View Code

1 # include
      
        2 # include
       
         3 # include
        
          4 # include
          5 using namespace std; 6 # define maxn 2005 //大小是2005，考点 7  8 char ss[3]; 9 int x;10 int d[maxn][maxn];11 char s1[maxn],s2[maxn];12 int max(int a,int b)13 {14     return a>b?a:b;15 }16 int i,j,n;17 int main()18 {19     map
          
           s;20     while(scanf("%d",&n)!=EOF)21     {22         s.clear(); //map函数没有这个的话，会出现Segmentation Fault，是下标出错23         for(i=0; i
           
            ans) ans=d[i+1][j+1];40 }41 }42 for(i=0;i<=n;i++)43 {44 for(j=0;j<=n;j++)45 printf(" %d ",d[i][j]);46 puts("");47 }48 printf("%d\n",ans);49 }50 return 0;51 }

转载地址：http://hdbxl.baihongyu.com/

你可能感兴趣的文章