P11366 题解

· · 题解

发现这个题和P8984很像，考虑那个题的做法。记 f_{n,k} 为序列长度为 n，查询时加法次数为 k 时修改至少要 f_{n,k} 次加法。根据那个题，我们有：

直接枚举 b,c，这样我们得到了一个时间复杂度 O(n^2k\log) 的做法。发现 (n,M_2) 只有 8 种，手动跑出最外层的 b,c 即可通过。

放一份没有最外层剪枝的代码。