3172.txt

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

Source

Problem Id:3172  User Id:fzk 
Memory:60K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>

unsigned int a[100];
unsigned int ans, c;

void search( int k, unsigned int rest, unsigned int sum ) {

	if( sum > ans )
		ans = sum;

	if( k < 0 || sum + rest <= ans )
		return;

	rest -= a[k-1] + a[k];

	sum += a[k-1];
	if( sum <= c ) {
		if( sum + a[k] < c )
			search( k-2, rest, sum + a[k] );
		else
			search( k-2, rest, sum );
	}

	sum -= a[k-1];
	if( sum + a[k] <= c )
		search( k-2, rest, sum + a[k] );
	else
		search( k-2, rest, sum );

}

int main( ) {
	int i, n;
	unsigned int t = 0;
	scanf( "%d%d", &n, &c );

	a[0] = 0;

	for( i=0; i<n; i++ ) {
		scanf( "%d", &a[i] );
		t += a[i];
	}

	if( n & 1 )
		a[n++] = 0;

	ans = 0;

	search( n-1, t, 0 );

	printf( "%d\n", ans );

	return 0;
}