算法难题：球堆叠问题

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 for 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 方法似乎可以解决它，但我不能完全制定递归。事实上，两个相邻的球可能有重叠的孩子，这让事情变得有点困难。

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)