UVa 10891 (博弈+DP) Game of Sum

最开始的时候思路就想错了，就不说错误的思路了。

因为这n个数的总和是一定的，所以在取数的时候不是让自己尽可能拿的最多，而是让对方尽量取得最少。

记忆化搜索(时间复杂度O(n³))：

d(i, j)表示原序列中第i个元素到第j个元素构成的子序列，先手取数能够得到的最大值。

sum(i, j) 表示从第i个元素到第j个元素的和

因为要让对手获得最小的分数，所以状态转移方程为：

d(i, j) = sum(i, j) - min{d(枚举所有可能剩给对手的序列), 0(0代表全部取完)}

s数组保存a中前i个元素的和,这样sum(i, j) = s[j] - s[i-1]

 1 #define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 100 + 10;
 9 int a[maxn], s[maxn], d[maxn][maxn], vis[maxn][maxn];
10 
11 int dp(int i, int j)
12 {
13     if(vis[i][j])
14         return d[i][j];
15     vis[i][j] = 1;
16     int m = 0;
17     for(int k = i + 1; k <= j; ++k)
18         m = min(m, dp(k, j));
19     for(int k = j - 1; k >= i; --k)
20         m = min(m, dp(i, k));
21     d[i][j] = s[j] - s[i-1] - m;
22     return d[i][j];
23 }
24 
25 int main(void)
26 {
27     #ifdef LOCAL
28         freopen("10891in.txt", "r", stdin);
29     #endif
30 
31     int n;
32     while(scanf("%d", &n) == 1 && n)
33     {
34         s[0] = 0;
35         for(int i = 1; i <= n; ++i)
36         {
37             scanf("%d", &a[i]);
38             s[i] = s[i-1] + a[i];
39         }
40         memset(vis, 0, sizeof(vis));
41         printf("%d
", 2*dp(1, n) - s[n]);
42     }
43     return 0;
44 }

代码君

递推(时间复杂度O(n²))：

令f(i, j) = min{d(i, j), d(i+1, j),,,d(j, j)}

g(i, j) = min{d(i, j), d(i, j-1),,,d(i, i)}

则状态转移方程可写成：

d(i, j) = min{f(i+1, j), g(i, j-1), 0}

f和g的递推为：

f(i, j) = min{d(i, j), f(i+1, j)}

g(i, j) = min{d(i, j), g(i, j-1)}

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 100 + 10;
 9 int a[maxn], s[maxn], d[maxn][maxn], f[maxn][maxn], g[maxn][maxn];
10 
11 int main(void)
12 {
13     #ifdef LOCAL
14         freopen("10891in.txt", "r", stdin);
15     #endif
16 
17     int n;
18     while(scanf("%d", &n) == 1 && n)
19     {
20         s[0] = 0;
21         for(int i = 1; i <= n; ++i)
22         {
23             scanf("%d", &a[i]);
24             s[i] = s[i-1] + a[i];
25         }
26         for(int i = 1; i <= n; ++i)//边界
27             d[i][i] = f[i][i] = g[i][i] = a[i];
28         for(int L = 1; L < n; ++L)
29             for(int i = 1; i + L <= n; ++i)
30             {
31                 int j = i + L;
32                 int m = 0;
33                 m = min(m, f[i+1][j]);
34                 m = min(m, g[i][j-1]);
35                 d[i][j] = s[j] - s[i-1] - m;
36                 //更新f和g
37                 f[i][j] = min(d[i][j], f[i+1][j]);
38                 g[i][j] = min(d[i][j], g[i][j-1]);
39             }
40 
41         printf("%d
", 2*d[1][n] - s[n]);
42     }
43     return 0;
44 }

代码君