EasyからHardへの誘導がいいね

解説

この制約では $k$ が小さいのでこれが小さいことを利用する解法を考える。

$dp[i][j] :=$ i日目において、前日 $[j, j + k)$ の区間を取った時の最大値

とdpを定義しよう。

そうすると、 $[l, l + k)$ の区間をとるとき、前と区間が被らないのであれば要素をそれぞれ足せばいいので

$dp[i][l] \leftarrow \max \left(dp[i][l], dp[i - 1][j] + \displaystyle \sum _ {t = j} ^ {j + k - 1} a _ t + \displaystyle \sum _ {t = l} ^ {l + k - 1} a _ t\right)$

となり、

$dp[i - 1][j] + \displaystyle \sum _ {t = j} ^ {j + k - 1} a _ t$

の部分を予め左右から累積maxをとればいいことがわかる。

問題は被るところで、被った場合は取る区間が上の場合と違い、1つの区間 $[l, r]$ とあらわせるので、

$dp[i][x] \leftarrow \max \left(dp[i][x], dp[i - 1][j] + \displaystyle \sum _ {t = l} ^ {r} a _ t\right)$

となる。ここで気をつけたいのが、 $k \leq 20$ と小さいので、被る区間は $O(k)$ である

以上から、 $O(nmk)$ で解くことができた。

Hardにつづく。。。

jupiro.hatenablog.com

提出コード

codeforces.com