3056.txt

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

Source

Problem Id:3056  User Id:fzk 
Memory:4008K  Time:3328MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>

int a[1010];
int n;
int ans[1010][1010];

int main( ) {
	int t, i, j, l, k, temp;
	scanf( "%d", &t );
	while( t-- ) {
		scanf( "%d", &n );
		
	
		for( i=0; i<n; i++ ) {
			scanf( "%d", &a[i] );
		}

		for( i=0; i<n; i++ ) {
			ans[i][i] = ans[i][i+1] = 0;
		}

		for( l=2; l<=n; l+=2 ) {
			for( i=0; i+l<=n; i++ ) {
				j = i+l;
				ans[i][j] = 0;
				for( k=i+1; k<j && ans[i][j] < j-i; k+=2 )
					if( ( temp = ans[i+1][k] + ans[k+1][j] + (a[i]==a[k]) ) > ans[i][j] )
						ans[i][j] = temp;
			}
		}

		printf( "%d\n", ans[0][n] );
	}
	return 0;
}