推 Gaogaigar: 推心得 12/14 10:05
推 jakeasa123: 感謝你的細心回應 12/14 17:56
推 s89162504: 高級酸XD 12/14 18:01
推 cutekid: 推喔(Y) 12/14 18:16
推 FRAXIS: 這問題有沒有可能用 BFS 解決? 12/15 07:06
推 FRAXIS: 如果最佳解有 self loop 應該是在最後一點 12/15 07:09
→ FRAXIS: 而如果沒有 self-loop 的話 應該可以忽略 cycle 12/15 07:10
→ FRAXIS: 不知道對不對 12/15 07:10
→ DJWS: 這個問題有一個性質: 正解按照地理座標排序仍是正解 12/15 08:10
→ DJWS: 因為它的起點在中央,所以地理座標設定成中間小、外圍大 12/15 08:10
→ DJWS: 也許這個性質可以用來節省時間 不過我還沒想出來 12/15 08:11
好像講錯了 當我沒說 XD
→ DJWS: 還有就是,因為可以一直停留,根據貪心的原則,問題變成了: 12/15 08:25
→ DJWS: 天數足夠的話,趕快跑去附近的最大值,然後躺著賺 12/15 08:26
^^^^(修正)遠方
→ DJWS: 天數不足的話,就留在起點附近的最大值,也是躺著賺 12/15 08:26
→ DJWS: 當盤面只有一維的話 應該是可以線性時間解出來 12/15 08:29
→ DJWS: 二維我就不清楚 交給ACM IOI選手想吧 他們腦筋比較好 12/15 08:30
※ 編輯: DJWS (118.167.32.224), 12/15/2016 08:39:30
→ outofyou: 這題可以設一個停止填表的中斷點,就是已填表格數(天數) 12/15 11:21
→ outofyou: ^^^對不起,好像不能確定,是我亂講 12/15 11:34
→ outofyou: 可以確定的是有最大值的那一格的累積值也已最大的時候。 12/17 12:01
推 aaaaajack: 枚舉終點 把weight改成終點值-原值做最短路徑 可以做到 12/18 00:36
→ aaaaajack: O(n^4 log n)不受天數影響 不過我不知道怎麼做到更快 12/18 00:36
推 hcsoso: 我想樓上的 n 指的是矩陣的邊長? 題目中 n 為天數. 12/18 14:45
→ hcsoso: 不論如何, 這題不難做到線性時間, 一次 BFS 加上證明一些 12/18 14:46
→ hcsoso: 最佳解的性質就行了. 12/18 14:46
推 hcsoso: 噢, 漏了一步, 得先做一次 DP 計算不停留的最大利益. 12/18 14:59
→ aaaaajack: 是邊長沒錯 沒注意原題的n是天數 12/19 00:51
推 hcsoso: 請教 aaaaajack 的算法若碰到負圈怎麼辦? 有負邊的圖中 12/19 06:57
→ hcsoso: 最短路徑 (simple path) 應是 NP-hard? 12/19 06:58
→ hcsoso: 啊, 可以先將所有負的位置移除, 最佳路徑不使用他們 12/19 06:59
→ DJWS: 樓上又在亂講 負值形成"口 回"這類形狀 路徑勢必要穿過去 12/19 07:02
→ DJWS: 不能刪除負值 也沒辦法"一齊加上足夠大數值"解決這種情況 12/19 07:04
→ DJWS: 況且根據原po給的盤面來看 應該是沒有負值... 12/19 07:05
推 hcsoso: 不是盤面上的負值, 而是 a 大算法中 終點值減原值可能為負 12/19 07:07
→ hcsoso: D 大提到的情形不會發生在最佳路徑上 12/19 07:09
→ DJWS: 這樣是我誤會了 對不起 12/19 07:23
推 aaaaajack: 負值直接忽略 ,證得終點必為最大值 否則改停在最大值 12/19 07:49
→ aaaaajack: *路徑上最大值 12/19 07:49
推 hcsoso: a大的算法可能有另外的問題。固定終點後也許有另一條獲 12/19 07:57
→ hcsoso: 利較少的但較短的路徑,在天數較少時也許才是最佳解。得 12/19 07:57
→ hcsoso: 計算 k 步內最短路徑才行? 12/19 07:57
推 hcsoso: 最糟的情形多一個 n^2 項。也許用動態最短路徑資料結構 12/19 08:02
→ hcsoso: 可以快一點,不過有點噁心… 12/19 08:02
→ DJWS: 根據貪心原則,至多算n^2天,DP至多O(n^4),不必搞那麼複雜 12/19 08:25
推 hcsoso: Good point. 12/19 08:42
→ aaaaajack: 你可能沒看懂我意思 終點值-原值算的就是「虧多少」 12/19 09:40
→ aaaaajack: 確實算n^2天即可 我本來是打算找找看有沒有單調性可以 12/19 09:41
→ aaaaajack: 利用 但情況似乎比我想的複雜 12/19 09:42
→ aaaaajack: 總之就是 已知最後要去哪裡賺 就挑虧最少的路徑過去 12/19 09:50
→ aaaaajack: 天數只影響要挑哪個終點 12/19 09:52
推 hcsoso: 請問如何依照天數決定終點呢?假設我們固定一終點,按終 12/19 10:27
→ hcsoso: 點值調整各位置值為虧損,並將忽略負值位置。若這時最佳 12/19 10:27
→ hcsoso: 路徑虧損10並花費10步,而有另一路徑前往同一終點虧損10 12/19 10:27
→ hcsoso: 0但花3步。當天數為三時如果只跑 Dijkstra 該點因最短路 12/19 10:27
→ hcsoso: 徑花費10步因此不會被選取,除非演算法紀錄對每個點每個 12/19 10:27
→ hcsoso: 天數的最短虧損路徑,但這就需要 k-Dijkstra 了。不知我 12/19 10:27
→ hcsoso: 是否誤解了? 12/19 10:27
推 aaaaajack: 抱歉,你說的沒錯,確實有問題 12/19 10:37
推 aaaaajack: 我誤解你原先天數的疑慮是optimality 12/19 10:41
→ aaaaajack: 但事實上feasibility就爆了Orz 12/19 10:42
→ DJWS: 想要單調性的話...的確是有啦! 12/19 17:06
→ DJWS: 盤面是一維的時候 類似於longest increasing subsequence 12/19 17:08
→ DJWS: 每個地點都有一個適合的天數區間 12/19 17:08
→ DJWS: 每當(地點座標,地點收益)變大、天數區間也隨之變大 12/19 17:10
→ DJWS: 預先計算每個地點的天數區間 之後可以暴搜/二分搜找答案 12/19 17:12
→ DJWS: 盤面是二維的話 我就不清楚了 12/19 17:14
→ aaaaajack: 一維路就只有一條 還不如直接枚舉 Orz 12/19 19:19
→ DJWS: 二維的路也就那麼幾條 不如直接dp? 12/20 05:30
→ aaaaajack: 囧 二維simple path有無窮多條啊 12/20 09:15
→ aaaaajack: 說錯 指數多條 12/20 09:16
→ aaaaajack: 現在問題不就是一維輕鬆線性 二維只能平方嗎 12/20 09:21
→ DJWS: 根據貪心原則,直達區域極值最賺,至多算n天,DP至多O(n^3) 12/20 22:02
→ DJWS: 如果再引入單調性 我覺得是有機會再降一些啦 12/20 22:05
→ DJWS: 修正一下,不是n天,是2n天 12/20 22:05
→ aaaaajack: 至多算n天就不對了 12/20 22:06
→ aaaaajack: 就像hcsoso那篇做法的問題 直達不會是最賺的 12/20 22:07
→ aaaaajack: 你可以設一些weight極小的格子強迫蛇行 達到n^2/2左右 12/20 22:07
→ aaaaajack: 天數還是太難處理 或許DP O(n^4)真的是最佳解 12/20 22:56