ABC 401-500/ABC438D - Tail of Snake - 競技プログラミング用 知識集積所

---

問題

ABC438D

必要知識

B以下レベルの内容は省略

• 動的計画法

考え方

問題文からはパっとはわかりづらいが、冷静に読んでみれば典型的な動的計画法。
i番目のパーツまで使ったときの、「最後を頭として使う」「最後を胴として使う」「最後を尾として使う」それぞれでの最大値を求めていけばよい。
最後のパーツまで計算を終えたときの「最後を尾として使う」の値が答え。

解答例

解答例

注意点

初期値に注意

1パーツ目の尾らしさが非常に高い場合、動的計画法の初期値を-1などにすると計算が壊れる場合がある。
2番目の尾の価値を足してもマイナスになるよう、-10^6より小さい値にしておくこと。

long long型を使う。

答えや動的計画法の計算途中の値はint型に収まらない場合がある。

別解