#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110;
const int M = 150;
int dp[N][N];
int main()
{
char a[110],b[110];
while(~scanf("%s%s",&a,&b))
{
memset(dp,0,sizeof(dp));
int len1 = strlen(a);
int len2 = strlen(b);
for(int i = 0; i < len1; i++)
{
for(int j = 0; j < len2; j++)
{
if(a[i] == b[j])
dp[i+1][j+1] = dp[i][j] + 1;
else
dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
}
}
printf("%d\n",len1+len2-dp[len1][len2]);
}
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1000000;

char a[MAXN+10],b[MAXN+10],c[MAXN+10],d[MAXN+10];
int f[2000][2000];

int main()
{
while(cin>>c>>d){
int lena=strlen(c);
int lenb=strlen(d);
for(int i=1; i<=lena; i++)
a[i]=c[i-1];
for(int i=1; i<=lenb; i++)
b[i]=d[i-1];
for(int i=1; i<=lena; i++)
for(int j=1; j<=lenb; j++){

if(a[i]==b[j])
f[i][j]=f[i-1][j-1]+1;
else
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
int ans=lena+lenb-f[lena][lenb];
cout<<ans<<endl;

}
system("pause");
return 0;
}

一个好的状态定义总能对应简洁精练的状态转移函数。
要有补集思想，善于从反面考虑问题。
一开始我没看出来是最大公用子序列。
之所以穿上马甲我就不认识你了，是因为没穿马甲时我也不太了解你。
要学会给学过的知识穿马甲，这样才能更深刻的理解知识。

for i:=1 to length(s1) do
for j:=1 to length(s2) do
if s1[i]=s2[j] then f[i,j]:=1+f[i-1,j-1]
else if f[i-1,j]>f[i,j-1] then f[i,j]:=f[i-1,j]
else f[i,j]:=f[i,j-1];

简单的LCS 求出最长公共子序列（不懂得见百度百科） 用两个字符串的长度去减去最长公共子序列的长 即为所求答案
注意无限输入

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=2014;
char a[maxn],b[maxn];
int l[maxn][maxn];
int main()
{
while(cin>>a>>b)
{ int lena=strlen(a),lenb=strlen(b);
for(int i=0;i<maxn;++i) {l[i][0]=0;l[0][i]=0;}
for(int i=1;i<=lena;++i)
for(int j=1;j<=lenb;++j)
{
if(a[i-1]==b[j-1]) l[i][j]=l[i-1][j-1]+1;
else l[i][j]=max(l[i-1][j],l[i][j-1]);
}
cout<<lena+lenb-l[lena][lenb]<<endl;}

//while(1);
return 0;
}

这一题 就一个测试点？？？
神马情况？？？？？？？？？？？？？？？？？？？？？？
编译成功

Free Pascal Compiler version 2.6.2 [2013/02/12] for i386

Copyright (c) 1993-2012 by Florian Klaempfl and others

Target OS: Win32 for i386

Compiling foo.pas

Linking foo.exe

17 lines compiled, 0.4 sec , 61232 bytes code, 12700 bytes data

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

Accepted, time = 0 ms, mem = 916 KiB, score = 100
？？？？？？？？

uses math;

var ch:char;s1,s2:string;f:array[0..120,0..120]of longint;

i,j,f1,f2:longint;

begin

while not eof do

begin
read(ch);s1:='';fillchar(f,sizeof(f),0);

while ch<>' ' do begin s1:=s1+ch;read(ch);end;

readln(s2);f1:=length(s1);f2:=length(s2);fillchar(f,sizeof(f),0);

for i:=1 to f1 do

for j:=1 to f2 do

if s1[i]=s2[j] then

f[i,j]:=max(max(f[i-1,j],f[i,j-1]),f[i-1,j-1]+1)

else f[i,j]:=max(max(f[i-1,j],f[i,j-1]),f[i-1,j-1]);

writeln(f1+f2-f[f1,f2]);

end;

end.

这个题很简单噻，，虽然我竟然CE，TLE，WA过很多次。。

题解+AC代码点击查看:
不懂得可以回复我会回答的共同进步噻~~

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

有不懂的可以看我的代码：http://hi.baidu.com/bgfumsjefublmtd/item/a8d8ea722bf62b066e29f6ca

var i,j,la,lb,q:longint;
sa,sb,sc:string;
f:array[0..1000,0..1000]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
begin
while not eof do
begin
readln(sc);
for i:=1 to length(sc) do
begin
if sc[i]=' ' then begin q:=i;
break;
end;
end;
sa:=copy(sc,1,q-1);
sb:=copy(sc,q+1,length(sc)-q);
la:=length(sa);
lb:=length(sb);
for i:=1 to la do
for j:=1 to lb do
begin
f[i,j]:=f[i-1,j];
if sa[i]=sb[j] then f[i,j]:=f[i-1,j-1]+1
else f[i,j]:=max(f[i-1,j],f[i,j-1]);
end;
writeln(length(sc)-1-f[la,lb]);
end;
end.

DP最长公共子序列。还是挺水的，以下是核心代码：
if x1[i]=x2[j]
then c[i,j]:=c[i-1,j-1]+1
else begin
if c[i-1,j]>c[i,j-1]
then c[i,j]:=c[i-1,j]
else c[i,j]:=c[i,j-1];
end;

#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define abs(x) ((x)>0?(x):-(x))
#define __max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
#define erep(i,repstt,repend) for(int i=repstt;i<=repend;i++)
#define inf 0x7f//2147483647
#define iinf 0x7fffffff
#define PI acos(-1.0)
#define NOBUG puts("No_Bug_Hear");
#define STOP system("pause");
#define FOUT freopen("out.txt","w",stdout);
#define FIN freopen("in.txt","r",stdin);
#define OUTCLOSE fclose(stdout);
#define INCLOSE fclose(stdin);
#define INIT(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int main(){
//FIN
//FOUT
char f1[103],f2[103];
int dp[103][103];
while(scanf(" %s %s",f1,f2)==2){
INIT(dp,0);
int len1=strlen(f1),len2=strlen(f2);
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(f1[i]==f2[j])
dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
}
printf("%d\n",len1+len2-dp[len1][len2]);
}
//INCLOSE
//OUTCLOSE
return 0;
}

5438

AC100 二星纪念+光棍节做光棍题+纪念今天NOIP大悲剧 感慨万千啊。。。

很明显。。最差情况下的合并长度是length(s1)+length(s2)。。然后我们需要减去其中重复的字母个数。。题目要求合并长度最小。。于是我们必须使重复字母个数最大。。故而题目转化成求两个字符串的LCS。。

唯一需要注意的就是在状态转移的时候i-1,j-1的非负判断。。

看了大家的题解..觉得我的方法略显垃圾....不过也是过了而且0ms。。。。是不是数据水呢。。。

#include

using namespace std;

int f[101][101]={0};

int main()

{

string str1,str2;

int i,j,n,m;

while(cin>>str1>>str2)

{

for(i=0;i

光棍节AC光棍题 感触良多

虽然参考了下面牛牛的题解。

光棍节做光棍题 祈祷来年不光棍

光棍节做光棍题......