P1070 [NOIP2009 普及組] 道路遊戲

先找出幾個細節：

(1)每一個時刻都必須有機器人位于環上。

(2)對于每個時刻 $i$ ,在 $ i $ 制造的機器人一定會花 \(1\) 的機關時間收集位于第 \(i\) 條邊上的金币。

(3)每次可以從任意位置開始重新選擇機器人。

然後可以選擇\(dp[i]\)表示時刻 \(i\) 的最大收益

(1)最開始發現這道題有環，習慣性地想到破環成鍊，然後可以發現破環成鍊的條件：

環隻有一層，且環是靜态的。

(2)dp有時需要盡量考慮\(dp[i]\)從\(dp[i-1]\)轉移的方法，因為這樣可以通過

用前面處理完的情況覆寫後面的情況以減少決策點。(雖然這道題跟這個好像沒什麼關系)

(3)dp不一定是從\(dp[i-k]\)向\(dp[i]\)轉移，可以考慮\(dp[i]\)向\(dp[i+k]\)轉移

ps:這個做法是跑不滿的\(O(n^3)\)暴力，正解有單調隊列優化，以後會考慮寫一下。