「vijos1111」小胖的水果
描述
xuzhenyi到大同水果店去买水果，但老板huyichen告诉他每次只能买一种，但是xuzhenyi想吃两种，于是在讨价还价之后，huyichen说只要xuzhenyi能把他想要的两种水果合并成一种，就能成功。你能帮他吗？
输入格式
输入文件包含两个要组合的水果名字。所有的名字最多有100个字母。(有若干行）
输出格式
对每一组测试数据，打印出一个最短的组合长度.
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<iostream> #include<cstring> using namespace std; int main() { int f[101][101]; string x,y; while(cin>>x>>y) { int lx=x.length(),ly=y.length(); x=" "+x;y=" "+y; memset(f,0,sizeof(f)); for(int i=1;i<=lx;i++) for(int j=1;j<=ly;j++) { if(x[i]==y[j])f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } cout<<lx+ly-f[lx][ly]<<endl; } return 0; } |
Subscribe
计数器 9294117
OI 课件=>
OI 课件=>