TIOJ 1029 A遊戲

第二次寫精煉很多

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#define INF 10000000

using namespace std;

// 1base

int arr[2000][2000] = {0};

int inp[2000];

int sum[2000];

int poi(int a, int b){

    if(a == b) return inp[a];

    if(arr[a][b] != 0) return arr[a][b];

    arr[a][b] = max(

        inp[a] + sum[b]-sum[a]-poi(a+1, b),

        inp[b] + sum[b-1]-sum[a-1]-poi(a, b-1)

    );

    return arr[a][b];

}

int main(){

    int n;scanf("%d", &n);

    sum[0] = 0;

    for(int lx = 1;lx <= n;lx++){

        scanf("%d", &inp[lx]);

        sum[lx] = sum[lx-1] + inp[lx];

    }

    int fst = poi(1, n);

    int scn = sum[n]-fst;

    printf("%d %d\n", fst, scn);

    return 0;

}