TIOJ 1029 A遊戲

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
int n, a[1005];
int dp[1005][1005];
int sum[1005];
int dfs(int x, int y){
    if(x == y) 
        return a[x];
    if(dp[x][y] > 0)
        return dp[x][y];

    int l = (sum[y] - sum[x]) - dfs(x+1, y) + a[x];
    int r = (sum[y-1] - sum[x-1]) - dfs(x,y-1) + a[y];
    if(l > r)
        return dp[x][y] = l;
    else
        return dp[x][y] = r;
}
int main(){
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i)
        scanf("%d",&a[i]);
    
    sum[1] = a[1];
    for (int i = 2; i <= n; ++i)
        sum[i] = sum[i-1] + a[i];

    for (int i = 1; i < n; ++i)
    for (int j = 1; j < n; ++j){
        dp[i][j] = 0;
        if(i == j)
            dp[i][j] = a[i];
    }     

    dfs(1, n); 

    printf("%d %d\n", dp[1][n], sum[n] - dp[1][n]);
}