yukicoder - No.1117 数列分割
ごめんなさい！！のところ全く読んでなかったです。修正しました。
解説
DPで解きます。dpの定義を
dp[i][j] := i番目まで見た時、j個分けている
としましょう。こうしたとき、愚直にDPを遷移させると以下のようなコードになると思います。
もちろん、これはですから間に合いません。
絶対値が厄介です。よく考えてみると、以下のように絶対値を取っても問題ありません。(負の場合は必ず正の場合より値が小さくなるからです)
これをもう少し変形させると、こうなります。
これで添え字kについて、まとめることができました！
よって後は上のコードでいうところの、max(dp[k][j-1] + sum[k])とmax(dp[k][j-1] - sum[k])にのみ注目したらいいことがわかるので、3つ目のfor文の部分はスライド最小値で代用できます。
以上で、で求めることができました。
提出コード
地味にきづいたんですが、ゆきこってコードふぁぼれるらしいので、参考にしたらふぁぼってくれると嬉しいな(⋈◍＞◡＜◍)。✧♡
