ZJU/ZOJ 1939 Compromise 解题报告

题目大意是找出两篇文章中的最长公告字串，并输出。

非常经典的DP，输出具体序列的处理方法有很多，我闲麻烦直接在DP过程中用ansistring记录当前位置的最长公告字串，DP完成后就直接输出......状态转移方程是f[i,j]=max(f[i-1,j],f[i,j-1])(word1[i]<>word2[j]);f[i,j]=max(f[i-1,j-1]+1,max(f[i-1,j],f[i,j-1]));(word1[i]=word2[j])。f[i,j]表示第一篇文章前i个单词与第二篇文章前j个单词匹配所得的最长公告字串的长度，word1[i]即第一篇文章的第i个单词，word2[j]即第二篇文章的第j个单词。

1648397 2008-09-20 14:20:38 Accepted 1939 FPC 0 648 IwfWcf