algorithm - 在 SPOJ 上寻找 MARTIAN 的 DP 解决方案的失败测试用例

Question

我正在尝试解决 the MARTIAN problem on SPOJ

我的算法如下:

1. 定义 dp[i][j]=max 可以在矩形 0,0 到 i,j 中开采的矿物数量。

2. 使用循环

   dp[i][j] = max(dp[i-1][j] + total amount of yeyenum
                               in the i-th row up to the j-th column,
                  dp[i][j-1] + total amount of bloggium
                               in the j-th column up to the cell i-th row)
   

然而，这种方法会产生 WA(错误答案)。有人可以给我提供一个这样的方法不起作用的测试用例吗？

我不是在寻找正确的算法，只是在寻找这种方法失败的测试用例。我一直无法自己找到错误。

Answer 1

在你的代码上试试这个(根据给定的例子修改):

4 4
0 0 10 60
1 3 10 0
4 2 1 3 
1 1 20 0
10 0 0 0
1 1 1 10
0 0 5 3
5 10 10 10
0 0

如果您从查看 [4][4] 开始，您会选择 Bloggium，因为向上可以得到 23 个 bloggium，而向左走只能得到 22 Yeyenum。但是，您会错过大量的 Yeyenum。

使用您的算法，您将得到 23 + 22 + 7 + 14 + 10 = 76。

如果您选择较大的 Yeyenum，您将得到 70 + 14 + 10 + 22 = 116(所有 Yeyenum，因为 bloggium 被封锁)。