ABC 401-500/ABC446D - Max Straight - 競技プログラミング用 知識集積所

---

問題

ABC446D

必要知識

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

• 動的計画法

考え方

「i番目の要素までで、jで終わるようなものを、最大どれくらいの長さまで作れるか？」を継承していく動的計画法。
iの値が1増えたとき、A[i]-1で終わる長さに1を足したものが元々のA[i]で終わる長さを更新できるかどうかだけ考えればよい。
よって、データは1つのmap※のデータを書き換えて使いまわしていけば十分。

全部終わったら、map※の中での最大値を答えればよい。

解答例

解答例

注意点

vectorでデータを持つことはできない。

Aの中身が最大10億までなので、vectorでデータを持つとメモリや初期化時間の問題が発生する。
map※でも座標圧縮※でもいいが、飛び飛びのキーを持てる構造を利用すること。

別解