JOI2018 本戦 B - 美術展

• 問題
• AC

最初から$A_1 \le A_2 \le ... \le A_N$であると仮定してよい。この場合、大きさの最大と最小が決まっていればその範囲にある美術品はすべて展示したほうが得なので、美術品の連続部分列だけ考えればすむ。

美術品$i$を展示しているとき、さらに$i+1$を展示すると得点は$B_{i+1}-(A_{i+1}-A_i)$だけ増えることに注目してDPする。$\operatorname{dp}[i] := i$まで展示するとした時の最大得点、として以下のように更新していけばよい:

$$\operatorname{dp}[i] \leftarrow \max(\operatorname{dp}[i-1] + B_{i}-(A_i-A_{i-1}), B_{i})$$

答えは$\max_{i \in [N]} \operatorname{dp}[i]$。

---

いわゆるKadane's algorithmっぽい感じなんだけど、なぜかそれをそのまま書いてしまってWAした。