Vijos1111-小胖的水果(LCS)

简介: Vijos1111-小胖的水果(LCS)

描述:


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;
}

相关文章
|
1月前
|
算法
AcWing 1343. 挤牛奶(每日一题)
AcWing 1343. 挤牛奶(每日一题)
|
6月前
|
算法
【随想】每日两题Day.9
【随想】每日两题
36 1
|
6月前
【随想】每日两题Day.16(实则一题)
【随想】每日两题Day.16(实则一题)
35 0
|
6月前
|
存储 算法
【随想】每日两题Day.20(实则一题)
【随想】每日两题Day.20(实则一题)
36 0
|
6月前
【随想】每日两题Day.3(实则一题)
【随想】每日两题Day.3
30 0
|
6月前
【随想】每日两题Day.5 (实则一题)
【随想】每日两题Day.5
30 0
|
6月前
|
存储
【随想】每日两题Day.10(实则一题)
【随想】每日两题Day.10(实则一题)
33 0
|
6月前
|
索引
【随想】每日两题Day.7
【随想】每日两题
29 0
|
6月前
【随想】每日两题Day.11
随想】每日两题Day.11
33 0
|
6月前
【随想】每日两题Day.6
【随想】每日两题
32 0