Lightoj 1031 Easy Game

http://lightoj.com/volume_showproblem.php?problem=1031

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int inf = 1 << 30;
4. const int MN = 111;
5. int dp[MN][MN];
6. bool seen[MN][MN];
7. int go(const vector<int> &nums, int i, int j) {
8.   if (i > j)
9.     return 0;
10.   if (i == j)
11.     return nums[i];
12.   if (seen[i][j])
13.     return dp[i][j];
14.   seen[i][j] = true;
15.   int accum = 0;
16.   int best = -inf;
17.   for (int k = i; k <= j; ++k) {
18.     accum += nums[k];
19.     best = max(best, accum - go(nums, k + 1, j));
20.   }
21.   accum = 0;
22.   for (int k = j; k >=  i; --k) {
23.     accum += nums[k];
24.     best = max(best, accum - go(nums, i, k - 1));
25.   }
26.   return dp[i][j] = best;
27. }
28. 
    
29. void solve() {
30.   int n;
31.   cin >> n;
32.   vector<int> nums(n);
33.   for (int i = 0; i < n; ++i) {
34.     cin >> nums[i];
35.   }
36.   memset(seen, 0, sizeof seen);
37.   printf("%d\n", go(nums, 0, n - 1));
38. }
39. 
    
40. int main() {
41.   int tc;
42.   cin >> tc;
43.   for (int i = 0; i < tc; ++i) {
44.     printf("Case %d: ", i + 1);
45.     solve();
46.   }
47.   return 0;
48. }
49.