2557.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"string.h"
int width[210],n;
int ans[210][210];
char fold[210];
bool init()
{
	int i,j;
	cin>>fold;
	if(cin.fail())return 0;
	n=strlen(fold);	
	for(i=0;i<n;i++)
	{
		for(j=1;i+j<n&&i-j>=0&&fold[i+j]+fold[i-j]=='A'+'V';j++)
			;
		width[i]=j;
	}
	return 1;
}
inline int get_ans(int a,int b)
{
	return (a>b)?0:ans[a][b];
}
void doit()
{
	int i,j,k,t,s1,s2,l;	
	for(i=0;i<n;i++)
	ans[i][i]=1;
	for(l=1;l<n;l++)
	for(i=0;i+l<n;i++)
	{
		j=i+l;
		ans[i][j]=9999;
		for(k=i;k<=j;k++)
		if( ( j-k<k-i ? j-k:k-i ) < width[k] )
		{
			s1 = get_ans(i,k-1);
			s2 = get_ans(k+1,j);
			t= 1+( s1 > s2 ? s1:s2 );			
			if(t<ans[i][j])ans[i][j]=t;
		}
	}
}
int main()
{
	while(init())
	{
		doit();
		cout<<ans[0][n-1]<<endl;
	}
	return 0;
}