UVa 10891 - Game of Sum

题目地址

描述

长度为 $n(1 \leq n \leq 100)$ 的整数序列,两个玩家 $\text{A}$ 和 $\text{B}$ 轮流取数。 $\text{A}$ 先取,每次每一个玩家只能从序列的一端开始取若干个数,但不能在序列的两端同时取。所有数都被取走后,统计 $\text{A}, \text{B}$ 玩家手上的数字的和作为各自的得分。我们假定 $\text{A}, \text{B}$ 两个人都很聪明且采用对自己最优的策略,求 $\text{A}$ 的得分减去 $\text{B}$ 的得分的结果。

分析

首先我们分析得到不管 $\text{A}, \text{B}$ 玩家怎样取,当前的序列一定会是原来的序列的一个连续的子序列。
自然而然的我们想到用 $dp[i][j]$ 来表示对于序列 $a[i \cdots j]$ 在双方都采用最优策略的时候先手能获得的最多的分数。

那么我们转移状态就要枚举是在序列的左边取还是在序列的右边取,分别是这样的 :

  • 从左边开始取,那么剩下的序列为 $a[k \cdots j] (i < k \leq j)$
  • 从右边开始取,那么生鲜的序列为 $a[i \cdots k] (i \leq k < j)$

我们要最小化剩下的序列以保证先手尽量获得更多的分数,那么有转移 :

括号里的 $0$ 表示把序列全部取完,这里不用每次 $\Theta(n)$ 扫一遍数组,只需要在读入序列 $a[]$ 的时候顺便计算一下前

缀和,那么

一共有 $\Theta(n^{2})$ 的状态,每一个状态有 $\Theta(n)$ 的转移,所以这样直接枚举转移时间复杂度为 $\Theta(n^{3})$,时间复杂度尚在接受范围内但是怎样能够更加优化呢?

考虑状态转移方程

我们完全可以把最小化的部分分为三部分来计算 :

  • 令 $f[i][j] = min(dp[i][j], dp[i + 1][j], dp[i + 1][j], \cdots, dp[j][j])$
  • 令 $g[i][j] = min(dp[i][j], dp[i][j - 1], dp[i][j - 2], \cdots, dp[i][i])$
  • 以及 $0$

那么状态转移方程可以改写为

其中

至此,我们可以在 $\Theta(1)$ 的时间复杂度内枚举转移,总时间复杂度降为 $\Theta(n^{2})$

动态规划的优化,不仅仅可以用单调队列,斜率优化这类数据结构或算法来优化,有时候不妨从动态规划的本质出发。

代码

时间复杂度$\Theta(n^{3})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//  Created by ZJYelizaveta on 2017年08月27日 星期日 18时26分39秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100 + 3;
const int INF = 0x3f3f3f3f;
int testCase;
int n;
int a[MAX_N], sum[MAX_N];
int dp[MAX_N][MAX_N], vis[MAX_N][MAX_N];

inline int solve(int i, int j) {
if (vis[i][j]) return dp[i][j];
vis[i][j] = 1;//
int minPart = 0;
for (int k = i + 1; k <= j; ++k) minPart = min(minPart, solve(k, j));
for (int k = i; k < j; ++k) minPart = min(minPart, solve(i, k));
dp[i][j] = sum[j] - sum[i - 1] - minPart;
return dp[i][j];
}

int main()
{
// freopen("test.in", "r", stdin);
while (scanf("%d", &n) && n) {
memset(sum, 0, sizeof sum); sum[0] = 0;
for (int i = 1; i <= n; ++i) {
a[i] = readIn();
sum[i] = sum[i - 1] + a[i];
}
// for (int i = 1; i <= n; ++i) printf("%d ", sum[i]); printf("\n");
memset(vis, 0, sizeof vis);
memset(dp, 0, sizeof dp);
printf("%d\n", 2 * solve(1, n) - sum[n]);
}
return 0;
}

时间复杂度$\Theta(n^{2})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//  Created by ZJYelizaveta on 2017年08月27日 星期日 19时06分10秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100 + 3;
const int INF = 0x3f3f3f3f;
int n;
int a[MAX_N], sum[MAX_N];
int dp[MAX_N][MAX_N], g[MAX_N][MAX_N], f[MAX_N][MAX_N];

int main()
{
while (scanf("%d", &n) && n) {
memset(sum, 0, sizeof sum); sum[0] = 0;
for (register int i = 1; i <= n; ++i) {
a[i] = readIn();
sum[i] = sum[i - 1] + a[i];
}

memset(dp, 0, sizeof dp);
memset(g, 0, sizeof g);
memset(f, 0, sizeof f);
for (register int i = 1; i <= n; ++i) dp[i][i] = g[i][i] = f[i][i] = a[i];

for (register int l = 1; l < n; ++l) {
for (register int i = 1; i + l <= n; ++i) {
int j = i + l, minPart = 0;
minPart = min(minPart, f[i + 1][j]);
minPart = min(minPart, g[i][j - 1]);

dp[i][j] = sum[j] - sum[i - 1] - minPart;
f[i][j] = min(dp[i][j], f[i + 1][j]);
g[i][j] = min(dp[i][j], g[i][j - 1]);//
}
}
printf("%d\n", 2 * dp[1][n] - sum[n]);
}
return 0;
}

Partager