> 我照着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;
> }
此程序还稍有问题，
1
21
1 1 1 2 1 1 1 3 1 1 1 1 1 3 3 3 3 3 3 3 3这组样例跑不出187=1+1+121+64