确定性做法。

如果问题在链上是非常容易的，可以做一个 $O(n^2k)$ dp 求出所有 $1\sim k$ 的答案。如果我们暴力枚举断点断环为链，那么解决所有 $1\sim k$ 的问题的复杂度就是 $O(n^3k)$。

暴力求出所有 $k=1,2,\dots,30$ 的答案。然后求出一个新的代价输出 $D_{i,j}$ 表示将圆弧 $[i,j]$ 使用恰好 $30$ 个弧覆盖的最小代价。然后以此为基础就可以暴力求出所有 $k=30,60,90,\dots,840$ 的答案了。

此时想要求解任何一个 $k$ 的答案，我们在环上枚举两个断点，分成 $k\bmod 30$ 的一段，和 $k-k\bmod 30$ 的一段，用我们上面求出的两种答案合并起来即可。

这里的 $30$ 取自 $\sqrt n$。所以复杂度实际上是 $O(n^3\sqrt n)$ 的。