USACO A Game

本人是看题解才过的，直到现在还弄不清什么叫作"best possible" opponent，本人认为这题是背包，而且还是比较奇怪的背包。

只贴代码了，如果有朋友理解题意的麻烦留个言，谢了！

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #define MAXN 110
04
05 long num[MAXN],sum[MAXN] = {},best[MAXN][MAXN] = {};
06 int N;
07
08 void init()
09 {
10     scanf("%d",&N);
11     int i;
12     for(i = 1;i <= N;i ++)
13         scanf("%ld",&num[i]);
14 }
15
16 long max(long a,long b)
17 {
18     if(a > b)    return a;
19     return b;
20 }
21
22 void solve()
23 {
24     int i,len;
25     for(i = 1;i <= N;i ++)
26     {
27         sum[i] = sum[i - 1] + num[i];
28         best[i][i] = num[i];
29     }
30     for(len = 1;len < N;len ++)
31         for(i = 1;i <= N - len;i ++)
32             best[i][i + len] = max(num[i] + sum[len + i] - sum[i] - best[i + 1][len + i],num[i + len] + sum[len + i - 1] - sum[i - 1] - best[i][len + i - 1]);    //这里sum的处理方法和NOIP2011质检员那题相同
33     printf("%ld %ld\n",best[1][N],sum[N] - best[1][N]);
34 }
35
36 int main()
37 {   
38     freopen("game1.in","r",stdin);
39     freopen("game1.out","w",stdout);
40     init();
41     solve();
42     return 0;
43 }