UVa 10891 Game of Sum

　　因为数的总和一定，所以用一个人得分越高，那么另一个人的得分越低。　　

　　用$dp[i][j]$表示从$[i, j]$开始游戏，先手能够取得的最高分。

　　转移通过枚举取的数的个数$k$来转移。因为你希望先手得分尽量高，所以另一个人的最高得分应尽量少。

　　$dp[i][j] = sum[i][j] - min {dp[i + k][j],dp[i][j - k]}$

　　但是发现计算$dp[i + k][j],dp[i][j - k]$的最小值的地方很重复，所以用一个$f[i][j]$储存前者的最优值，$g[i][j]$储存后者的最优值。

　　这样就将代码的时间复杂度优化到O(n²)

Code

 1 /**
 2  * uva
 3  * Problem#10891
 4  * Accepted
 5  * Time:0ms
 6  */
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cctype>
10 #include<cstring>
11 #include<cstdlib>
12 #include<cmath>
13 #include<sstream>
14 #include<algorithm>
15 #include<map>
16 #include<set>
17 #include<queue>
18 #include<vector>
19 #include<stack>
20 using namespace std;
21 typedef bool boolean;
22 #define INF 0xfffffff
23 #define smin(a, b) a = min(a, b)
24 #define smax(a, b) a = max(a, b)
25 template<typename T>
26 inline void readInteger(T& u){
27     char x;
28     long long aFlag = 1;
29     while(!isdigit((x = getchar())) && x != '-');
30     if(x == '-'){
31         x = getchar();
32         aFlag = -1;
33     }
34     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
35     ungetc(x, stdin);
36     u *= aFlag;
37 }
38 
39 int n;
40 int *list;
41 int f[101][101];
42 int g[101][101];
43 int dp[101][101];
44 
45 inline boolean init(){
46     readInteger(n);
47     if(n == 0)    return false;
48     list = new int[(const int)(n + 1)];
49     for(int i = 1; i <= n; i++){
50         readInteger(list[i]);
51     }
52     return true;
53 }
54 
55 int *sum;
56 inline void getSum(){
57     sum = new int[(const int)(n + 1)];
58     sum[0] = 0;
59     for(int i = 1; i <= n; i++)
60         sum[i] = sum[i - 1] + list[i];
61 }
62 
63 inline void solve(){
64     memset(f, 0x7f, sizeof(f));
65     memset(g, 0x7f, sizeof(g));
66     for(int i = 1; i <= n; i++)    f[i][i] = g[i][i] = dp[i][i] = list[i];
67     for(int k = 1; k < n; k++){
68         for(int i = 1; i + k <= n; i++){
69             int j = i + k;
70             int m = 0;
71             smin(m, f[i + 1][j]);
72             smin(m, g[i][j - 1]);
73             dp[i][j] = sum[j] - sum[i - 1] - m;
74             f[i][j] = min(f[i + 1][j], dp[i][j]);
75             g[i][j] = min(g[i][j - 1], dp[i][j]);
76         }
77     }
78     printf("%d
", dp[1][n] * 2 - sum[n]);
79     delete[] list;
80     delete[] sum;
81 }
82 
83 int main(){
84     while(init()){
85         getSum();
86         solve();
87     }
88     return 0;
89 }