ABC 401-500/ABC456F - Plan Holidays - 競技プログラミング用 知識集積所

---

問題

ABC456F

必要知識

B以下レベルの内容は省略

• トロピカル半環※
• segment木※

考え方

長さK以上の休日を要求されているが、K+2以上にする意味は特にない。
というのは、コストを払っている最後の1つをキャンセルしても長さが最低でもK以上残るため。
よって、長さKまたはK+1の休日を作る最低コストを考えればよい。

L日目からR日目までについて、「R日目のコストを払って全部を休日にする」「R日目のコストは払わず、R-1日目まで全部を休日にする」の2つの情報を求めることを考える。
これを

|x[R] y[R]|

という1行2列の行列で表現する。

ここからRの値を1増加させると情報は

|x[R+1] y[R+1]| = |min(x[R],y[R])+a[R+1] x[R]|

に変化する。
これは、トロピカル半環※上で行列

|a[R+1]  0  |
|a[R+1] INF |

を右から掛けることに相当する。

よって、segment木※を用いることで、L日目からR日目までについて合成した行列を高速に作ることができる。
これを

|INF 0|

に右からかけたときに、左側にL日目からR日目まで全部休みにする最低コスト、右側にL日目からR-1日目まで全部休みにする最低コストが出てくる。
（実はかけなくても、行列を得た段階で左下と右下に入っている）

従って、（0-indexで）

• i日目からi+K日目までのK+1日の合成をした左下と右下（i=0,1,……,N-K-1）
• N-K日目からN-1日目までのK日を合成した左下

の中の最小値を求めれば答えとなる。

解答例

解答例

注意点

long long型を使用する。

Aの値をたくさん足すので、int型からはみ出る。
答えはもちろん、途中の値についてもlong long型を用いること。

別解