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)\)暴力，正解有单调队列优化，以后会考虑写一下。