原文链接: https://leetcode-cn.com/problems/stone-game-v

英文原文

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice's is initially zero.

Return the maximum score that Alice can obtain.

 

Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.

Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28

Example 3:

Input: stoneValue = [4]
Output: 0

 

Constraints:

• 1 <= stoneValue.length <= 500
• 1 <= stoneValue[i] <= 106

中文题目

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

 

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

 

提示：

• 1 <= stoneValue.length <= 500
• 1 <= stoneValue[i] <= 10^6

通过代码

高赞题解

解题思路

1、状态标识

这题状态是比较显然的

$f_{l, r}$ 代表剩下第 $l \sim r$ 块石头时，最大得分是多少

2、直观转移

我们先预处理 $sum_{l, r} = \sum\limits_{i=l}^{r}a_i$ 以便后续计算

考虑最简单的决策，枚举一个中间点$mid$,

(1) $sum_{l, mid} \leq sum_{mid + 1, r}$ 时，则

$f_{l, r} = \max(f_{l, r}, (sum_{l, mid} + f_{l, mid}))$

(2) $sum_{l, mid} \geq sum_{mid + 1, r}$ 时，则

$f_{l, r} = \max(f_{l, r}, (sum_{mid + 1, r} + f_{mid + 1, r}))$

3、优化转移

因为长度有 500，三方的转移复杂度是有点高的，因此我们要考虑优化这个转移

在求 $f_{l, r}$ 的时候，因为石子数都是正数，所以存在一个中间点 $g_{l, r}$，使得：

(1) $mid \in [l, g_{l, r}- 1]$ 时，$sum_{l, mid} < sum_{mid + 1, r}$

(2) $mid \in [g_{l, r}, r]$ 时，$sum_{l, mid} \geq sum_{mid + 1, r}$

显然 $l$ 固定时，$g_{l, r}$ 随着 $r$ 增大不会递减，因为我们可以用 $O(n^2)$ 的时间预处理出 $g_{l, r}$

求出 g_{l, r} 后，我们考虑优化转移：

(1) $mid$ 在 $g_{l, r}$ 左边时，$f_{l, r}$ 只需要和 $(f_{l, mid} + sum_{l, mid})$ 作比较

(2) 其余情况，$f_{l, r}$ 只需要和 $(f_{mid + 1, r} + sum_{mid + 1, r})$ 作比较

（注意两边和相等的情况要特殊处理一下）

那么我们只需要计算出

$maxL_{l, r} = \max\limits_{i=l}^{r}(f_{l, i} + sum_{l, i})$

$maxR_{l, r} = \max\limits_{i=l}^{r}(f_{i, r} + sum_{i, r})$

就可以做到 $O(1)$ 转移

显然有

$maxL_{l, r} = \max(maxL_{l, r - 1}, (f_{l, r} + sum_{l, r}))$

$maxR_{l, r} = \max(maxR_{l + 1, r}, (f_{l, r} + sum_{l, r}))$

因此 $maxL$，$maxR$ 在求 $f$ 的过程中都可以 $O(1)$ 求出来

这样就做到了 $O(n^2)$ 预处理，$O(n^2)$ 动态规划

总复杂度 $O(n^2)$

[]
const int N = 505;
int s[N][N], g[N][N], f[N][N], mxl[N][N], mxr[N][N];
class Solution {
public:
    int stoneGameV(vector<int> &a) {
        int n = a.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j] = g[i][j] = s[i][j] = 0;
                mxl[i][j] = mxr[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            s[i][i] = a[i];
            g[i][i] = i;
            for (int j = i + 1; j < n; j++) {
                s[i][j] = s[i][j - 1] + a[j];
                int now = g[i][j - 1];
                while (s[i][j] - s[i][now] > s[i][now]) {
                    now++;
                }
                g[i][j] = now;
            }
        }

        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                int mid = g[l][r];
                int ls = s[l][mid];
                int rs = s[mid + 1][r];
                if (ls == rs) {
                    f[l][r] = max(f[l][r], mxl[l][mid]);
                    f[l][r] = max(f[l][r], mxr[mid + 1][r]);
                } else {
                    if (mid > l) {
                        int ls = s[l][mid - 1];
                        f[l][r] = max(f[l][r], mxl[l][mid - 1]);
                    }
                    if (mid < r) {
                        int rs = s[mid + 1][r];
                        f[l][r] = max(f[l][r], mxr[mid + 1][r]);
                    }
                }
                int v = f[l][r] + s[l][r];
                if (l == r) {
                    mxl[l][r] = mxr[l][r] = v;
                } else {
                    mxl[l][r] = max(v, mxl[l][r - 1]);
                    mxr[l][r] = max(v, mxr[l + 1][r]);
                }
            }
        }
        return f[0][n - 1];
    }
};

统计信息

通过次数	提交次数	AC比率
4091	10726	38.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言