三四十分求助

我的思路是从中某个位置分别向前和向后取两个子串，然后找到最大公式子序列，分别剩下多少个就是需要插入的数据。分两种情况讨论，补完是偶数个的字符串和补完是奇数个的，也就是当前位置这一个不是两个子串的或者是某个子串的。但是问题出现了，两个都考虑到是30分，正确的是1、5、10测试点。只考虑为偶数的是40分，正确的是1、7、8、10。只考虑为奇数的是30分，正确的是3、4、5 这就让人很费解了，求大佬指点

CPP

#include<bits/stdc++.h>
using namespace std;
int fun(string s,string t)
{
	int m,n,i,j;
	m=s.size();
	n=t.size();
	int a[m+1][n+1];
	for(i=0;i<=m;i++)
		a[i][0]=0;
	for(i=0;i<=n;i++)
		a[0][i]=0;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			if(s[i]==t[j])
				a[i][j]=a[i-1][j-1]+1;
			else
				if(a[i-1][j]>a[i][j-1])
					a[i][j]=a[i-1][j];
				else
					a[i][j]=a[i][j-1];
		}
	//if(a[m][n]==143)
		//cout<<s<<endl<<t<<endl;
	return a[m][n];
}
int main()
{
	string s,t,w;
	cin>>s;
	int i,j,ans=0x7fffffff,x,y;
	y=s.size();
	for(i=0;s[i];i++)
	{
		t="";
		for(j=i-1;j>=0;j--)
			t+=s[j];
		w="";
		for(j=i+1;j<y;j++)
			w+=s[j];
		x=y-1-2*fun(t,w);
		if(x<ans)
			ans=x;
		t=s[i]+t;
		x=y-2*fun(t,w);
		if(x<ans)
			ans=x;
	}
	cout<<ans;
	return 0;
}

讨论操作

回复

相关推荐

三四十分求助