3186.txt

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

Source

Problem Id:3186  User Id:fzk 
Memory:92K  Time:77MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>

int a[2001];
int sum[2001];
int mem[2][2001], *ans1 = mem[0], *ans2 = mem[1], n;

void input( ) {
	scanf( "%d\n", &n );
	
	for( int i=0; i<n; i++ )
		scanf( "%d", a+i );
	
	sum[n] = 0;

	for( i=n-1; i>=0; i-- )
		sum[i] = a[i] + sum[i+1];
}

void doit( ) {
	int i, l;
	for( i=0; i<n; i++ )
		ans1[i] = a[i];
	for( l=2; l<=n; l++ ) {
		for( i=0; i<=n-l; i++ ) {
			ans2[i] = ans1[i];
			if( ans1[i+1] > ans2[i] )
				ans2[i] = ans1[i+1];
			ans2[i] += sum[i]-sum[i+l];
		}
		std::swap( ans1, ans2 );
	}
	
	printf( "%d\n", ans1[0] );

}

int main( ) {
	input( );
	doit( );
	return 0;
}