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

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

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

答案就是字符串的长度减去两者的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;
}
     

两串的长度和减去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;
}

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

}

模板题啊

var
s1,s:string;
k,l1,l2,i,j:longint;
a:array [0..105,0..105] of longint;
begin
while not(eof) do
begin
readln(s);
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.

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
read(f);
i:=1;
while f<>' ' do
begin
s[i]:=f;
i:=i+1;
read(f);
end;
readln(t);
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.

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

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

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

逗我就一个数据点？？？
#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;
}

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

题解+代码

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
readln(t);
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.

```

一开始被坑得好惨
```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;
}
```

一个点？
编译成功

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

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

#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]);
    }
}

**
#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]);
}
}
**

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;
read(c);s:='';
while c<>' ' do
begin
s:=s+c;
i:=i+1;
read(c);
end;
readln(ss);
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!