# 76 条题解

• @ 2017-10-21 10:45:15
``````//Simple LCS
#include <bits/stdc++.h>
using namespace std;
int dp[200][200];
int main()
{
char str1[200],str2[200];
while(~scanf("%s%s",str1+1,str2+1))
{
int len1 = strlen(str1+1);
int len2 = strlen(str2+1);
memset(dp, 0, sizeof(dp));
for(int i = 1; str1[i]; i++)
for(int j = 1; str2[j]; j++)
if(str1[i] == str2[j])
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", dp[len1][len2]);
int ans = dp[len1][len2];
ans = len1 + len2 - ans;
printf("%d\n", ans);
}
return 0;
}
``````
• @ 2017-07-20 08:29:25

#include<bits/stdc++.h>
using namespace std;
string s1,s2; int f[201][201];
int main(){
while (cin>>s1>>s2)
{
memset(f,0,sizeof(f));
for (int i=1; i<=s1.length(); i++)
for (int j=1; j<=s2.length(); j++)
if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
cout<<s1.length()+s2.length()-f[s1.length()][s2.length()]<<endl;
}
return 0;
}

• @ 2017-06-03 16:30:43
``````#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int f[114][114];
string a,b;

int main()
{
while(cin>>a)
{
cin>>b;
int alen=int(a.length());
int blen=int(b.length());
int flg=0;
for(int i=0;i<blen;i++)
{
if(flg==0)
{
if(a[0]==b[i])
{
flg=1;
f[0][i]=1;
}
else f[0][i]=0;
}
else f[0][i]=1;
}
flg=0;
for(int i=0;i<alen;i++)
{
if(flg==0)
{
if(b[0]==a[i])
{
flg=1;
f[i][0]=1;
}
else f[i][0]=0;
}
else f[i][0]=1;
}
for(int i=1;i<alen;i++)
{
for(int j=1;j<blen;j++)
{
int tt=f[i-1][j]>f[i][j-1]?f[i-1][j]:f[i][j-1];
if(a[i]==b[j])
{
tt=f[i-1][j-1]+1;
}
f[i][j]=tt;
}
}
cout<<alen+blen-f[alen-1][blen-1]<<endl;
}
}

``````
• @ 2017-05-08 07:59:28

答案就是字符串的长度减去两者的LCS的长度即可
所以直接写一个LCS的DP模板就好啦
然后答案就出来咯

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

int f[101][101];
char a[102],b[102];

int main()
{
while(scanf("%s %s",a,b)==2)
{
int c1=strlen(a);
int c2=strlen(b);
for(int i=0;i<=c1;i++)
f[i][0]=0;
for(int i=0;i<=c2;i++)
f[0][i]=0;
for(int i=1;i<=c1;i++)
for(int j=1;j<=c2;j++)
if(a[i-1]==b[j-1])
f[i][j]=f[i-1][j-1]+1;
else
f[i][j]=max(f[i-1][j],f[i][j-1]);
int k=f[c1][c2];
cout<<c1+c2-k<<endl;}
return 0;
}

``````
• @ 2019-03-10 10:27:26

两串的长度和减去LCS的长度即可

``````#include<cstdio>
#include<algorithm>
#include<string>
#include<iostream>
#include<cstring>
using namespace std;
int d[101][101];
string a,b;
int main(){
ios::sync_with_stdio(false);
while(cin>>a>>b){
memset(d,0,sizeof(d));
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
if(a[i]==b[j]) d[i+1][j+1]=d[i][j]+1;
else d[i+1][j+1] = max(d[i+1][j],d[i][j+1]);
}
}
cout<<a.size()+b.size()-d[a.size()][b.size()]<<endl;
}
return 0;
}

``````
• @ 2018-04-18 13:02:10

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define q 250
typedef long long ll;

string a,b;
int main()
{

while(cin>>a>>b)
{
ll f[q][q]={0},a1,b1;
a1=a.size() ;
b1=b.size() ;
for(int i=1;i<=a1;i++)
for(int j=1;j<=b1;j++)
{
if(a[i-1]==b[j-1])
f[i][j]=f[i-1][j-1]+1;
else
f[i][j]=max(f[i][j-1],f[i-1][j]);

}
cout<<a1+b1-f[a1][b1]<<endl;

}
return 0;

}

模板题啊

• @ 2016-03-16 20:06:20

var
s1,s:string;
k,l1,l2,i,j:longint;
a:array [0..105,0..105] of longint;
begin
while not(eof) do
begin
k:=pos(' ',s);
s1:=copy(s,1,k-1);
delete(s,1,k);
l1:=length(s1);
l2:=length(s);
fillchar(a,sizeof(a),0);
for i:=1 to l1 do
for j:=1 to l2 do
if (s1[i]=s[j]) then a[i,j]:=a[i-1,j-1]+1
else if (a[i,j-1]>a[i-1,j]) then a[i,j]:=a[i,j-1]
else a[i,j]:=a[i-1,j];
writeln(l1+l2-a[l1,l2]);
end;
end.

• @ 2015-07-17 08:37:50

20AC+3星纪念
program zuichanggonggongzichuan;
var
a:array[0..1000,0..1000] of longint;
s,t:string;
i,j,k,l,m,n:longint;
f:char;
function max(a,b:longint):longint;
begin
if a>b
then exit(a)
else exit(b);
end;
begin
while not eof do
begin
i:=1;
while f<>' ' do
begin
s[i]:=f;
i:=i+1;
end;
m:=i-1;
n:=length(t);
for i:=1 to m do
for j:=1 to n do
if s[i]=t[j]
then a[i,j]:=a[i-1,j-1]+1
else a[i,j]:=max(a[i-1,j],a[i,j-1]);
writeln(m+n-a[m,n]);
end;
end.

• @ 2019-03-26 20:04:50

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int f[114][114];
string a,b;

int main()
{
while(cin>>a)
{
cin>>b;
int alen=int(a.length());
int blen=int(b.length());
int flg=0;
for(int i=0;i<blen;i++)
{
if(flg==0)
{
if(a[0]==b[i])
{
flg=1;
f[0][i]=1;
}
else f[0][i]=0;
}
else f[0][i]=1;
}
flg=0;
for(int i=0;i<alen;i++)
{
if(flg==0)
{
if(b[0]==a[i])
{
flg=1;
f[i][0]=1;
}
else f[i][0]=0;
}
else f[i][0]=1;
}
for(int i=1;i<alen;i++)
{
for(int j=1;j<blen;j++)
{
int tt=f[i-1][j]>f[i][j-1]?f[i-1][j]:f[i][j-1];
if(a[i]==b[j])
{
tt=f[i-1][j-1]+1;
}
f[i][j]=tt;
}
}
cout<<alen+blen-f[alen-1][blen-1]<<endl;
}
}

• @ 2018-08-06 16:19:31
``````#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

string s,s2;
int f[101][101];
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while (cin>>s>>s2) {
memset(f,0,sizeof f);
int n=s.size(),m=s2.size();
FOR(i,n) FOR(j,m) {
f[i][j]=max(f[i][j],f[i][j-1]);
f[i][j]=max(f[i][j],f[i-1][j]);
if (s[i-1]==s2[j-1]) f[i][j]=max(f[i][j],1+f[i-1][j-1]);
}
cout<<n+m-f[n][m]<<endl;
}
return 0;
}
``````
• @ 2017-09-23 11:31:40
``````while True:
try:
a, b = input().split()
dp =  [[0 for i in range(101)] for i in range(101)]
for i in range(len(a)+1):
for j in range(len(b)+1):
dp[i][j] = 0
for i in range(1, len(a)+1):
for j in range(1, len(b)+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(len(a) + len(b) - dp[len(a)][len(b)])
except EOFError:
break

``````
• @ 2017-05-03 17:34:39

逗我就一个数据点？？？
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
char s[101],t[101];
int f[101][101];
while(cin>>s>>t)
{
memset(f,0,sizeof(f));
for(int i=0;i<strlen(s);i++){
for(int j=0;j<strlen(t);j++){
if(s[i]==t[j]) f[i+1][j+1]=f[i][j]+1;
else f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
}
}
cout<<strlen(s)+strlen(t)-f[strlen(s)][strlen(t)]<<endl;
}
return 0;
}

• @ 2016-09-23 15:08:40

ans=字符串长度和－LCS（相同字符个数）

• @ 2016-08-16 00:12:52
• @ 2016-05-11 12:29:04

SCS=长度和-LCS
```pascal
uses math;
function lcs(a,b:string):integer;
var dp:array[0..101,0..101] of integer;
i,j:integer;
begin
for i:=0 to length(a) do dp[i,0]:=0;
for j:=0 to length(b) do dp[0,j]:=0;
for i:=1 to length(a) do
for j:=1 to length(b) do
if a[i]=b[j] then dp[i,j]:=dp[i-1,j-1]+1
else dp[i,j]:=max(dp[i-1,j],dp[i,j-1]);
lcs:=dp[length(a),length(b)];
end;

var i,z:integer;t:string;
begin
while not eof do begin
for i:=1 to length(t) do
if t[i]=' ' then begin z:=i;break end;
writeln(length(t)-1-lcs(copy(t,1,z-1),copy(t,z+1,length(t)-z)));
end;
end.

```

• @ 2016-05-09 18:11:49

一开始被坑得好惨
```c++
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;

string ss1, ss2;
int ans;
int f[110][110];

void lcs () {
int l1 = ss1.size();
int l2 = ss2.size();
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (ss1[i] == ss2[j]) f[i + 1][j + 1] = f[i][j] + 1;
else {
f[i + 1][j + 1] = max (f[i + 1][j], f[i][j + 1]);
}
}
}
ans = l1 + l2 - f[l1][l2];
}

int main ()
{
//freopen ("in.txt", "r", stdin);
while (cin >> ss1 >> ss2) {
lcs();
cout << ans << endl;
}
return 0;
}
```

• @ 2016-03-21 17:08:40

一个点？
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 544 KiB, score = 100

Accepted, time = 0 ms, mem = 544 KiB, score = 100

• @ 2016-02-17 15:55:49
``````#include<stdio.h>
#include<string.h>
char a[105],b[105];
int lcs[105][105]={0};
inline int max(int a,int b){ return a>b?a:b; }
int main(){
while(~scanf("%s %s",a,b)){
int n=strlen(a);
int m=strlen(b);
memset(lcs,0,sizeof lcs);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(a[i]==b[j]) lcs[i+1][j+1]=lcs[i][j]+1;
else lcs[i+1][j+1]=max(lcs[i][j+1],lcs[i+1][j]);
printf("%d\n",n+m-lcs[n][m]);
}
}
``````
• @ 2016-02-17 15:55:19

**
#include<stdio.h>
#include<string.h>
char a[105],b[105];
int lcs[105][105]={0};
inline int max(int a,int b){ return a>b?a:b; }
int main(){
while(~scanf("%s %s",a,b)){
int n=strlen(a);
int m=strlen(b);
memset(lcs,0,sizeof lcs);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(a[i]==b[j]) lcs[i+1][j+1]=lcs[i][j]+1;
else lcs[i+1][j+1]=max(lcs[i][j+1],lcs[i+1][j]);
printf("%d\n",n+m-lcs[n][m]);
}
}
**

• @ 2015-12-13 11:33:18

program p1111;
var a:array[0..1001,0..1001] of integer;
c:char;
s,ss:string;
i,j,k,m,n,js:longint;
begin
assign(input,'p1111.in');
assign(output,'p1111.out');
reset(input);
rewrite(output);
while not eof do
begin
fillchar(a,sizeof(a),0);
i:=1;
while c<>' ' do
begin
s:=s+c;
i:=i+1;
end;
m:=i-1;
n:=length(ss);
for i:=1 to m do
begin
for j:=1 to n do
begin
if s[i]=ss[j] then a[i,j]:=a[i-1,j-1]+1
else
begin
if a[i-1,j]>a[i,j-1] then a[i,j]:=a[i-1,j]
else a[i,j]:=a[i,j-1];
end;
end;
end;
writeln(m+n-a[m,n]);
end;
close(input);
close(output);
end.
瞬间爆炸,完成AC!

ID
1111

4

2824

1270

45%

8