【思维、dp】【MGOI R1】魔法环

· · 题解

这是下派验题人题解。前往 T3 题解。

解法

先提一下显然的 O(n^3k) 做法。

钦定 0\sim n-1 中的一个为初始激活点。然后断环为链，后面接一个初始点形成长度为 n+1 的序列。

设 dp_{i,j} 表示考虑到 i 点且已经激活 j 个点时的最小贡献。我们有转移

dp_{i,j+1}=\min\limits_{p=1}^{n-1}\{dp_{p,j}+val(p,i)\}.

上面只是 j< k 的情况，为使其满足至少 k 个的条件。还应有

dp_{i,k}=\min\limits_{p=1}^{n-1}\{dp_{p,k}+val(p,i)\}.

这里的贡献函数 val 可以 O(1) 计算，不在优化范畴内。

枚举 i,j,p，转移即可。但这并不能通过本题。考虑优化。

我们先来考虑一个结论：选 \boldsymbol{0} 一定不劣。

证明一下，对于一个没有选 0 的状态，加上 0 后，0 的贡献从初始某值变为了 0^2=0 而不会改变其他结点的贡献，这是容易证明的。所以选 0 一定不劣。

那么我们在「钦定」这一步直接钦定 0 开始激活不就好了吗！因为 0 是必选的。

所以将复杂度降到了 O(n^2k)，可以通过。

Bonus

初始的题意是「选定恰好 k 个点激活」，但难以证明在这种情况下选 0 不劣。出题组和我都不太会！欢迎提供证明/证伪。