2018.10.24 NOIP模拟 小 C 的数组(二分+dp)

时间:2021-11-22 16:32:20

传送门

考试自己yyyyyy的乱搞的没过大样例二分+dp二分+dp二分+dp过了606060把我自己都吓到了!

这么说来乱搞跟被卡常的正解比只少101010分?

那我考场不打其他暴力想正解血亏啊。

正解同样是二分+dp。

f[i]f[i]f[i]表示i不变且前面全部满足当前要求时最少需要改几个数。

然后用f[i+1]f[i+1]f[i+1]~f[n]f[n]f[n]转移一下就行了。

代码