2013年8月29日

UVa 10891 - Game of Sum

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    int num[101], sum[101] = {}, dp[101][101];
    for (int i = 1; i <= n; i++) {
      scanf("%d", &num[i]);
      sum[i] = sum[i - 1] + num[i];
      dp[i][i] = num[i];
    }
    for (int l = 2; l <= n; l++) {
      for (int i = 1; i + l - 1 <= n; i++) {
        int j = i + l - 1;
        int s = sum[j] - sum[i - 1];
        dp[i][j] = s;
        for (int k = i; k < j; k++) {
          dp[i][j] = max(dp[i][j], s - min(dp[i][k], dp[k + 1][j]));
        }
      }
    }
    printf("%d\n", dp[1][n] - (sum[n] - dp[1][n]));
  }
  return 0;
}

1 則留言: