显然每个后缀最多操作一次,于是暴力枚举即可,时间复杂度 O(2n)\mathcal{O}(2^n)O(2n)。
可能存在一些复杂度较大的神奇做法。
签到题啊,假设令 S0=0S_0=0S0=0,那么答案就是 max(∑i=1n[Si≠Si−1]−1,0)\max(\sum_{i=1}^n [S_i\ne S_{i-1}]-1,0)max(∑i=1n[Si=Si−1]−1,0)。为什么呢?
注意到相邻相同的字母是可以缩在一起的,那么问题变成了 01010101... 这种交替串将其变成不降串最小操作次数,这是非常简单的,从后往前依次翻转即可。
01010101...
例如 01010,先变成 01011,再变成 01000,最后变成 01111。
01010
01011
01000
01111
使用您的 Hydro 通用账户