algorithm - 算法难题：球堆积问题

Question

我正在尝试解决这个问题：https ://www.urionlinejudge.com.br/judge/en/problems/view/1312

XYZ 电视频道正在开发一个新的游戏节目，参赛者必须做出一些选择才能获得奖品。游戏由一堆三角形的球组成，每个球都有一个整数值，如下例所示。

参赛者必须选择他要拿的球，他的奖品是这些球的价值的总和。然而，参赛者只有在他也直接将球直接拿在球上时才能拿走任何给定的球。这可能需要使用相同的规则采取额外的球。请注意，参赛者可以选择不拿任何球，在这种情况下，奖金为零。

电视节目导演关心参赛者可以为给定筹码获得的最高奖金。由于他是你的老板，而且他不知道如何回答这个问题，所以他将这个任务分配给了你。

输入

每个测试用例都用几行来描述。第一行包含一个整数N，表示堆栈的行数（1 ≤ N ≤ 1000）。接下来的N行中的第 i 个包含i个 ^整数B ij （_-105 ≤ B _ij ≤ 105 对于 1 ≤ j ≤ i ≤ N）；数字B _ij是堆栈的第i 行中^第j ^个球的值（第一行是最上面的一个，如果是最左边的一个，则在每一行中第一个球）。

最后一个测试用例后面是一个包含一个零的行。

输出

Sample Input  | Sample Output
4             |   7 
3             |   0
-5 3          |   6
-8 2 -8       |
3 9 -2 7      |
2             |
-2            |
1 -10         |
3             |
1             |
-5 3          |
6 -4 1        |
0             |

我很想知道如何解决这个问题的一两个指针。

似乎可以使用 DP 方法解决，但我不能完全制定递归。两个相邻的球可能有重叠的孩子这一事实使事情变得有些困难。

标签： algorithmdynamic-programming

Answer 1

这是 DP，但我们要横向而不是自上而下。让我们将球堆稍微向左倾斜，这样我们就可以将整个堆栈视为一系列列。

 3  3 -8  7
-5  2 -2
-8  9
 3

从这个角度看，游戏规则变成：如果我们想拿球，我们也需要把球拿在上面，然后把球直接放在左边。

现在，解决问题。我们将为S[i, j]每个球计算一个数量——这表示如果取位置 [i, j] 的球（第 i 列顶部的第 j 个球），我们可以达到的最佳总和，同时只考虑第一个我列。

我声称以下递归成立（具有一些合理的初始条件）：

S[i, j] = MAX(S[i-1, j] + C[i, j], S[i, j+1])

其中C[i, j]是第 i 列中前 j 个球的总和。

让我们分解一下。我们要计算S[i, j]。

• 我们必须在 [i, j] 处接球。现在让我们假设这是我们从该列中取出的最底部的球。
• 这要求将其上方这一列中的所有球都拿走，总和（包括 [i, j] 本身）为C[i, j]。
• 它还需要在 [i-1, j] 处接球（当然，除非我们在最左边的列）。我们知道，S[i-1, j]根据定义，拿下这个球的最佳总和是 。
• 所以最好的总和是: S[i-1, j] + C[i, j]，或者只是C[i, j]最左边的列。
• 但是我们可以选择不同的方式，从这个列中取更多的球（如果我们有更多的球）。S[i-1, j] + C[i, j]我们需要计算并从、等中取出最大值S[i-1, j+1] + C[i, j+1]，一直到堆的底部。稍加归纳，很容易看出这等于MAX(S[i-1, j] + C[i, j], S[i, j+1])。

实现现在应该很明显了。我们逐列处理堆栈，在每一列C[i, j]中从上到下计算部分和，然后S[i, j]从下到上计算。S[i, j]最后，只需将我们遇到的最大值（或 0）作为答案。

这与球的数量呈线性关系，因此 O(N^2)。

为了说明，这里是给定示例的 ( C[i, j], S[i, j]) 对。

(  3, 3) ( 3,7) ( -8,-1)  (7,6)
( -2,-2) ( 5,7) (-10,-3) 
(-10,-7) (14,7)
( -7,-7)