我照着lrj书上的算法做的，但是不知道怎么优化啊
#include <iostream>
#define sqr(a) ( (a) * (a) )
int s[201][201][201] , cl[201] , len[201] , po[201][201][201][101];

int f(int i , int j , int k)
{
	if(s[i][j][k] > -1) return s[i][j][k];
	int p , tmp;
	tmp = f(i , j-1 , 0 ) + sqr(k+len[j]) ;
	for (p = i ; p < j ; p++ )
	{
		if(cl[p]==cl[j])tmp = std::max( tmp , f(i , p , k+len[j])+f(p+1 , j-1, 0) );
	}
	s[i][j][k] = tmp;
	return tmp;
}

int main()
{
	int t , n , i ,  j , k , m , a ;
	scanf("%d" , &t);
	for (int ca=1; ca <= t ; ca++ )
	{
		scanf("%d" , &n);
		i = 1;
		scanf("%d" , &a);
		cl[i] = a;
		len[i] = 1;
		n--;
		while(n--)
		{
			scanf("%d" , &a);
			if (a == cl[i])
			{
				len[i]++;
			}
			else 
			{
				cl[++i] = a;
				len[i] = 1;
			}
		}
		m = i;
		for(i = 0 ; i <= m ; i++)
			for ( j = 0; j <= m ; j++ )
				for ( k = 0; k <= m ; k++ )
					s[i][j][k] = -1;
		for( i = 1 ; i <= m ; i++) s[i][i-1][0] = 0;
		a = f( 1 , m , 0);
		printf("Case %d: %d\n" , ca , a);
	}
	return 0;
}

• Re:这个题怎么优化啊~我4500ms过掉的，请大牛指教 (1225) huicpc0838 2010-12-05 10:00:09