abcbdcab	bdcabc
amnpnrmn	bnrpanm
abcbdab		abcbdab
abc		abacabc
abacada		bcd
abdecfg		acgbde
dynamic		programming
programming 	contest
textbook	txtbokk
abcfbc         	abfcab
abcfbc		abfc
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa


answer：
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;

}

• Re:测试数据以及我的小代码 (2377) allh123 2013-05-09 21:52:18
• Re:测试数据以及我的小代码 (25) allh123 2013-05-09 21:53:05