vijos1111 小胖的水果

vijos1111 小胖的水果

(​​ 描述

xuzhenyi到大同水果店去买水果，但老板huyichen告诉他每次只能买一种，但是xuzhenyi想吃两种，于是在讨价还价之后，huyichen说只要xuzhenyi能把他想要的两种水果合并成一种，就能成功。你能帮他吗？ 格式 输入格式

输入文件包含两个要组合的水果名字。所有的名字最多有100个字母。(有若干行） 输出格式

对每一组测试数据，打印出一个最短的组合长度. 样例1 样例输入1

apple peach ananas banana pear peach

Copy 样例输出1

8 7 6

Copy 来源

huyichen

非常经典的Lcs问题 之前一直疑惑的为什么lcs这么转移 看了一篇blog的文章 也明白的差不多了

假定Z=﹤z1，⋯，zk﹥∈LCS(X , Y)。 若xm=yn（最后一个字符相同），则不难用反证法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时，问题化归成求Xm-1与Yn-1的LCS（LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1）。 若xm≠yn，则亦不难用反证法证明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立，若zk≠xm则有Z∈LCS(Xm-1 , Y)，类似的，若zk≠yn 则有Z∈LCS(X , Yn-1)。此时，问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为：max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。由于上述当xm≠yn的情况中，求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度，这两个问题不是相互独立的：两者都需要求LCS(Xm-1，Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。

#include#include#includeusing namespace std;int f[110][110];char s1[110],s2[110];int main(){ freopen("vijos1111.in","r",stdin); while(~scanf("%s%s",s1+1,s2+1)){ int n1=strlen(s1+1),n2=strlen(s2+1);memset(f,0,sizeof(f)); for (int i=1;i<=n1;++i){ for (int j=1;j<=n2;++j){ if (s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } }printf("%d\n",n1+n2-f[n1][n2]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。