Listing 1522

#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;
}