Listing 1520

#include "cgamelib.h"
#define MN 2001
#define min(a,b) (((a)<(b))?(a):(b))
int n;
int d[MN], s[MN];
void input()
{
	initialize();
	n = getN();
	for (int i = 1; i <= n; i++) {
		d[i] = getValue(i-1);
		s[i] = s[i-1]+d[i];
	}
}
int c[MN][MN], x[MN][MN];
void getC()
{
	int i, j, k, p;
	
	for (i = 1; i <= n; i++) {
		x[i][i] = i; c[i][i] = d[i];
	}
	for (k = 2; k <= n; k++) {
		for (i = 1; i+k-1 <= n; i++) {
			j = i+k-1;
			c[i][j] = 0;
			for (p = x[i][j-1]; p <= x[i+1][j]; p++) {
				if (c[i][j] < min(c[i][p],c[p+1][j])) {
					c[i][j] = min(c[i][p],c[p+1][j]);
					x[i][j] = p;
				}
			}
			c[i][j] += d[j]-d[i];
		}
	}
}
void process()
{
	int i=1, j=n;
	
	for (;;) {
		if (move(x[i][j]-1)) i = x[i][j]+1;
		else j = x[i][j]-1;			
	}
}
int main()
{
	input();
	getC();
	process();
	return 0;
}