描述:
xuzhenyi到大同水果店去买水果,但老板huyichen告诉他每次只能买一种,但是xuzhenyi想吃两种,于是在讨价还价之后,huyichen说只要xuzhenyi能把他想要的两种水果合并成一种,就能成功。你能帮他吗?
格式:
输入格式
输入文件包含两个要组合的水果名字。所有的名字最多有100个字母。(有若干行)
输出格式
对每一组测试数据,打印出一个最短的组合长度.
样例1:
样例输入1
apple peach ananas banana pear peach
样例输出1
8 7 6
AC Code:
#include<stdio.h> #include<string.h> #include<stdlib.h> #define max(x,y) (x>y ? x:y) #define N 210 int dp[N][N],len1,len2; char s1[N],s2[N]; int main() { while(~scanf("%s%s",s1,s2)) { len1=strlen(s1); len2=strlen(s2); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; }else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } printf("%d\n",len1+len2-dp[len1][len2]); } return 0; }