問題リンク
EasyからHardへの誘導がいいね
解説
この制約ではが小さいのでこれが小さいことを利用する解法を考える。
i日目において、前日の区間を取った時の最大値
とdpを定義しよう。
そうすると、の区間をとるとき、前と区間が被らないのであれば要素をそれぞれ足せばいいので
となり、
の部分を予め左右から累積maxをとればいいことがわかる。
問題は被るところで、被った場合は取る区間が上の場合と違い、1つの区間とあらわせるので、
となる。ここで気をつけたいのが、と小さいので、被る区間はである
以上から、で解くことができた。
Hardにつづく。。。
jupiro.hatenablog.com
提出コード
codeforces.com