尋找在SPOJ

Question

失敗的測試案例DP解決火星

我試圖解決the MARTIAN problem on SPOJ

我的算法如下：

1. 定義可以在矩形中開採礦石的dp[i][j]=max量形式爲0,0 to 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，因爲博客被封鎖）。