跪求大神的解題報告

 跪求大神的解題報告

我的想法是dp[][][2]左掃1次 、右掃1次 

左掃 dp[r][c][0] = a[r][c] + max( dp[r][c-1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

右掃 dp[r][c][1] = a[r][c] + max( dp[r][c+1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

 跪求大神的解題報告

你要DFS你大概要剪枝剪到只剩一塊葉綠素才有可能不TLE吧(完全不剪全跑=3^(10000*30)次)

 跪求大神的解題報告

我的想法是dp[][][2]左掃1次 、右掃1次 

左掃 dp[r][c][0] = a[r][c] + max( dp[r][c-1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

右掃 dp[r][c][1] = a[r][c] + max( dp[r][c+1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

右掃為 dp[r][c][1] = a[r][c] + max( dp[r][c+1][1], max(dp[r-1][c][0],dp[r-1][c][1] ) )  才對

 跪求大神的解題報告

你要DFS你大概要剪枝剪到只剩一塊葉綠素才有可能不TLE吧(完全不剪全跑=3^(10000*30)次)

共m列每一列 左掃一次 n、右掃一次 n  應該 50*2*10000 而已，為何是 3^(10000*30)次？
而且我已AC 

 跪求大神的解題報告

你要DFS你大概要剪枝剪到只剩一塊葉綠素才有可能不TLE吧(完全不剪全跑=3^(10000*30)次)

共m列每一列 左掃一次 n、右掃一次 n  應該 50*2*10000 而已，為何是 3^(10000*30)次？
而且我已AC 

6506752

es611543 (afa)

f314. 3. 勇者修煉 -- 2020年10月APCS

AC (41ms, 4.3MB)

CPP

2020-10-19 00:24

如果造成誤會很抱歉，但你是DP，我是在回版主的標題，他看起來想用DFS

 跪求大神的解題報告

你要DFS你大概要剪枝剪到只剩一塊葉綠素才有可能不TLE吧(完全不剪全跑=3^(10000*30)次)

共m列每一列 左掃一次 n、右掃一次 n  應該 50*2*10000 而已，為何是 3^(10000*30)次？
而且我已AC 

6506752

es611543 (afa)

f314. 3. 勇者修煉 -- 2020年10月APCS

AC (41ms, 4.3MB)

CPP

2020-10-19 00:24

如果造成誤會很抱歉，但你是DP，我是在回版主的標題，他看起來想用DFS

想問問那在什麼樣的時機才適合用DFS呢

DP又是什麼概念

小弟我目前程度只在apcs 3級而已

諸如此類的演算法其實並沒有很了解其原理及用法

 跪求大神的解題報告

你要DFS你大概要剪枝剪到只剩一塊葉綠素才有可能不TLE吧(完全不剪全跑=3^(10000*30)次)

共m列每一列 左掃一次 n、右掃一次 n  應該 50*2*10000 而已，為何是 3^(10000*30)次？
而且我已AC 

6506752

es611543 (afa)

f314. 3. 勇者修煉 -- 2020年10月APCS

AC (41ms, 4.3MB)

CPP

2020-10-19 00:24

如果造成誤會很抱歉，但你是DP，我是在回版主的標題，他看起來想用DFS

想問問那在什麼樣的時機才適合用DFS呢

DP又是什麼概念

小弟我目前程度只在apcs 3級而已

諸如此類的演算法其實並沒有很了解其原理及用法

你在求類似這種最佳路徑，最棒組合，最小花費等等類似的題目時
當你發現你的算法幾乎把所有情況都跑了一遍->你很有可能用DFS，BFS窮舉了
當你發現不知道為啥，但重複的情況你幾乎沒算到，每一步都是最好的，而且常常可以用一個數學是去表達每一步之間的關西->DP，你如果不知道你怎麼AC的，那你是天生的DP大師

 跪求大神的解題報告

我的想法是dp[][][2]左掃1次 、右掃1次 

左掃 dp[r][c][0] = a[r][c] + max( dp[r][c-1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

右掃 dp[r][c][1] = a[r][c] + max( dp[r][c+1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

請問有人在UVA或leetcode看過這種題目嗎，我在leetcode的DP分類找好久都找不到

通常動態規劃的題目並沒有一定的形式，動態規劃算不上是種演算法或是資料結構，只是一種工具( 好比你學會遞迴，總不會把他當作某種 Case By Case 產生的對應工具而已 )

關於你問的 DFS 和 DP 使用時機差別：首先 你的 DFS 如果是指暴力法那我舉個經典的01背包問題變型板 - 分兩堆為例，a276 和 b116 作為對照，兩者解法不同你可以想想看。

背包問題本身屬於 NP - problem ，代表存在「某些限制」下這個題目能再有限的時間內解出，少了這個限制就無法。

基本上動態規劃的核心在於兩點 (1)狀態定義  (2) 狀態轉移，而通常解題報告提到的都是狀態轉移( 描述狀態轉移時一定要先定義狀態 )。

如果題目沒有明說狀態轉移方式那就需要從 TopDown 去思考，有了狀態轉移就可以做 BottomUp，後者因為少了檢查某個狀態有沒有計算過的成本時間上會快許多。

一般來說練習動態規劃方式無疑是從經典的模版題開始：背包問題, 零錢兌換, 最長共同子序列 , 嚴格遞(非)增(減)子序列，練習這些的目的是學會上述提到的2點並知道什麼時候不能用。

最後就是寫考題，考試多半會限制時間導致題目一定要作動態規劃的 BottomUp 比如SG函數，而要完成 BottomUp 有個嚴格的限制就是更新現在的狀態前需要確保所有子狀態已經更新完。

基於這個限制你可以去察看題目會提到在某些時候「不能回頭」或是「不能回溯」，動態規劃和二分法很像難在怎麼知道這個題目可以用，所以做之前一定要知道「限制」。

以上希望有回答到你的問題。

 跪求大神的解題報告

我的想法是dp[][][2]左掃1次 、右掃1次 

左掃 dp[r][c][0] = a[r][c] + max( dp[r][c-1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

右掃 dp[r][c][1] = a[r][c] + max( dp[r][c+1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

剛剛AC了 感激不盡

通常動態規劃的題目並沒有一定的形式，動態規劃算不上是種演算法或是資料結構，只是一種工具( 好比你學會遞迴，總不會把他當作某種 Case By Case 產生的對應工具而已 )

關於你問的 DFS 和 DP 使用時機差別：首先 你的 DFS 如果是指暴力法那我舉個經典的01背包問題變型板 - 分兩堆為例，a276 和 b116 作為對照，兩者解法不同你可以想想看。

背包問題本身屬於 NP - problem ，代表存在「某些限制」下這個題目能再有限的時間內解出，少了這個限制就無法。

基本上動態規劃的核心在於兩點 (1)狀態定義  (2) 狀態轉移，而通常解題報告提到的都是狀態轉移( 描述狀態轉移時一定要先定義狀態 )。

如果題目沒有明說狀態轉移方式那就需要從 TopDown 去思考，有了狀態轉移就可以做 BottomUp，後者因為少了檢查某個狀態有沒有計算過的成本時間上會快許多。

一般來說練習動態規劃方式無疑是從經典的模版題開始：背包問題, 零錢兌換, 最長共同子序列 , 嚴格遞(非)增(減)子序列，練習這些的目的是學會上述提到的2點並知道什麼時候不能用。

最後就是寫考題，考試多半會限制時間導致題目一定要作動態規劃的 BottomUp 比如SG函數，而要完成 BottomUp 有個嚴格的限制就是更新現在的狀態前需要確保所有子狀態已經更新完。

基於這個限制你可以去察看題目會提到在某些時候「不能回頭」或是「不能回溯」，動態規劃和二分法很像難在怎麼知道這個題目可以用，所以做之前一定要知道「限制」。

以上希望有回答到你的問題。

 

感謝兩位大神的講解，剛剛去做了a693,a694兩題，感覺有點初步了解DP的概念了。

只是小弟我有個疑問，在做類似這種題目時，使用cin, cout會比scanf,printf慢上許多，甚至會TLE。

想請問這個是zerojudge本身的問題，還是這兩種輸出輸入的用途差異導致的呢?

感謝兩位大神的講解，剛剛去做了a693,a694兩題，感覺有點初步了解DP的概念了。

只是小弟我有個疑問，在做類似這種題目時，使用cin, cout會比scanf,printf慢上許多，甚至會TLE。

想請問這個是zerojudge本身的問題，還是這兩種輸出輸入的用途差異導致的呢?

可以google下這個"cin.tie(0); ios::sync_with_stdio(false);"

 跪求大神的解題報告

我的想法是dp[][][2]左掃1次 、右掃1次 

左掃 dp[r][c][0] = a[r][c] + max( dp[r][c-1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

右掃 dp[r][c][1] = a[r][c] + max( dp[r][c+1][0], max(dp[r-1][c][0],dp[r-1][c][1] ) ) 

剛剛AC了 感激不盡

剛剛AC了 感激不盡  +1

不過上面是不是有些地方要小小修改…？

不過這個想法很讚！謝謝