じゅぴろの日記(⋈◍＞◡＜◍)。✧♡

SoundHound Programming Contest 2018 Masters Tournament 本戦 - B - Neutralize

問題リンク

かなり典型だと思うのですが、詰まってる人が多かったので

解説

dp[i] := $i$ 番目まで見た時の最大値としましょう。

$i$ 番目を取るときは、

$dp[i] \leftarrow \max (dp[i], dp[i - 1] + b[i])$

です。取らないときは $i$ 番目から $K$ 個以上を消すことができるので、

$dp[i] \leftarrow \max (dp[i], dp[j]) \ \ (0 \le j \le i - K)$

です。よって $i$ 番目までのdpの最大値を管理しながらやれば、遷移は $O(1)$ で求まるので $O(n)$ で求めることができました。

提出コード