传送门

考试自己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]转移一下就行了。

代码