ABC140 D. Face Produces Unhappiness - phyllo’s algorithm note

N人の人が一列に並んでおり、各人が左を向いているか右を向いているかの情報が文字列Sで与えられる。
各人は、目の前の人が自分と同じ方向を向いていればhappyであり、そうでなければunhappyである。

ここで、0回以上K回以下で、好きな回数だけ以下の操作ができる

このとき、happyな人の人数は最大で何人にすることができるか？

操作によって変化する量を確認する。
すると、変化する部分は、指定したl,rの付近のみで、l-1とl、rとr+1の文字のみを考えればよいことがわかる。

今、unhappyな人をできるだけ減らしたいので、そのような人の部分を操作によって減らしていければ良い。
例えば、
LLLLRRRRRRLLLLL
のような場合は、Rの部分を操作するとすべてLになり、unhappyな人がその両端の2人分減らすことができる。

したがって、隣り合う文字列が異なる個数Xを求めて、最大K回まで-2していくことができるので、最終的に「N-1-max(0, X-2*K)」が答えになる。