ZJU/ZOJ 1642 Match for Bonus 解题报告

题目大意是两个字符串进行匹配，给定每个字符匹配的得分，每次匹配完成后该字符前的字符串将被删除，求最高匹配得分。

带权LCS（最长公共子串）模型。用f[i,j]表示第一个字符串前i个字符与第二个字符串前j个字符匹配的最高得分，则f[i,j]=max(f[i-1,j-1]+v[s1[i]],max(f[i-1,j],f[i,j-1]))(s1[i]=s2[j]);f[i,j]=max(f[i-1,j],f[i,j-1])(s1[i]<>s2[j]);s1[i]表示第一个字符串的第i个字符，s2[j]表示第二个字符串第j个字符，v[s1[i]]表示s1[i]的匹配得分。

1653610    2008-10-02 10:01:55     Accepted    1642    FPC    70    16040    IwfWcf