2236.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2236 on 2006-05-17 at 13:50:21 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int CN = 1024;

int main()
{
	int sub[CN], n, card[CN], i, j, t;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		memset(sub, 0, sizeof(sub));
		for(i = 0; i < n; i++) scanf("%d", &card[i]);
		for(i = n-1; i >= 0; i--)
			for(j = i; j < n; j++)
				if((j-i)&1) sub[j] = max(sub[j]+card[i], sub[j-1]+card[j]);
				else if(card[i] >= card[j]) sub[j] = sub[j]-card[i];
				else sub[j] = sub[j-1]-card[j];
		printf("In game %d, the greedy strategy might lose by as many as %d points.\n", t, sub[n-1]);
	}
	
	return 0;
}