Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 测试数据以及我的小代码

Posted by liuqingfang at 2012-08-25 23:54:06 on Problem 1458
```abcbdcab	bdcabc
amnpnrmn	bnrpanm
abcbdab		abcbdab
abc		abacabc
abdecfg		acgbde
dynamic		programming
programming 	contest
textbook	txtbokk
abcfbc         	abfcab
abcfbc		abfc
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

5
4
7
3
3
4
3
2
6
4
4
0
200

#include <iostream>
using namespace std;

#define maxn 1002

int f[maxn][maxn];
char str1[maxn],str2[maxn];

int find(char &c,char str[],int n)
{
for(int i = n;i>=0;i--)
{
if(str[i]==c)
return i;
}
return -1;
}

//n1,n2指从有字母的位置
int dp(int n1,int n2)
{
if(f[n1][n2]!=-1)
return f[n1][n2];

int index = find(str1[n1],str2,n2);
if(n1==0)
{
if(index==-1)//最后一个都不是
{
f[n1][n2]=0;
return 0;
}else{//最后一个是
f[n1][n2]=1;
return 1;
}
}else
{
if(index==-1)//去找下一个
{
f[n1][n2]=dp(n1-1,n2);
return f[n1][n2];
}else{//最后一个字母有出处，考虑要还是不要
int a = dp(n1-1,n2);//不要
int b = dp(n1-1,index-1);//要
if(a>b+1)
f[n1][n2]=a;
else
f[n1][n2]=b+1;
return f[n1][n2];
}
}
}

int main()
{
while (cin >> str1 >> str2)
{
int len1 = strlen(str1)-1;
int len2 = strlen(str2)-1;
memset(f,-1,sizeof(f));
dp(len1,len2);
printf("%d\n",f[len1][len2]);
/*for(int i=0;i<=len1;i++)
{
for(int j=0;j<=len2;j++)
printf("%d  ",f[i][j]);
printf("\n");
}*/
}
return 0;

}```

Followed by: