みんなのプロコン2019 D - Ears

解法

適当に実験をすると、散歩後の石の個数は、座標が小さい順に、次のような区間でわけることができます。

石が0個の区間
石の個数が2個以上の偶数の区間
石の個数が奇数の区間
石の個数が2個以上の偶数の区間
石が0個の区間

ただし、それぞれの区間の幅が0の可能性もあります。
ということで、今現在どの区間にいるか、という情報を持たせつつDPを行います。上の5つのパターンに、上から0,1,2,3,4と番号を割り振ります。
$dp[i][j] = i$ 番目の耳まで見て、そこがパターン $j$ だったときの、操作の最小値
とすると、
$b_{ij} = i$ 番目の耳がパターン $j$ だった際にかかる操作回数
を用いて、
$dp[i + 1][j] = min(dp[i][k] + b_{ij}) (だたし、k \leqq j)$
と計算することができます。
$b_{ij}$ は、