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

相关文章
|
6月前
|
机器学习/深度学习 并行计算 定位技术
NYOJ22-吝啬的国度
NYOJ22-吝啬的国度
29 0
|
6月前
洛谷P1204 or SSL-1088 USACO 1.2 挤牛奶
洛谷P1204 or SSL-1088 USACO 1.2 挤牛奶
【USACO题库】1.2.1 Milking Cows挤牛奶
【USACO题库】1.2.1 Milking Cows挤牛奶
75 0
|
6月前
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
41 0
|
测试技术
华为机试HJ77:火车进站
华为机试HJ77:火车进站
126 1
|
12月前
|
算法 Java
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
代码随想录算法训练营第三十四天 | LeetCode 860. 柠檬水找零、406. 根据身高重建队列、452. 用最少数量的箭引爆气球
64 0
|
机器学习/深度学习 算法 数据安全/隐私保护
华为机试HJ28:素数伴侣
华为机试HJ28:素数伴侣
100 0
|
大数据 网络架构 索引
Leecode134加油站打卡
Leecode134加油站打卡
89 0
Leecode134加油站打卡
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
代码随想录刷题|LeetCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球