暑い日々AC
※はじめに言っておきますが、皆さんにとってはこの問題は楽勝だというのは知っているので、決してイキリとかそういう風に思わないでください。誰だって自分が解けなかった問題が解けるようになると嬉しいのです。(たとえどんなに簡単な問題であろうと)
感想枠(無駄)
先ほどACしたのですが、泣きそうなくらいうれしかったです。
なぜなら、答えを見ずに最後まで自分で解けたからです(eiyaさんなど他の大先輩からの手は借りさせていただきましたが、直接的な解法は教えてもらってません)
こんなに問題が解けて嬉しいことはなかったので、競技プログラミングのなかで自分にとって最も大きい成功体験だったと思います!
解いている途中は、こんなに時間を無駄にしていいのかとか思っていたのですが、今思えば、そこで解答を見ていた方が時間の無駄だったと思います。
なんか偉そうで申し訳ないのですが、本当に最後まであきらめずに解けて良かったです
はい、偉そうですね(なかったことにしてください)
問題の概要、自分の大まかな考え方
大きな方針
- DP
- その日の最大、最小の派手さを決める
- DPの中でもメモ化再帰
注意するべきところ
それぞれの差の最大値を求めていれば、最適解が求まるとは限らない(何枚目かという違いがあるから)
深さ優先探索は価値はあとで足さないとdpテーブルに入れる時に死ぬ
自分の解答、および方法
Submission #1356472 - 第12回日本情報オリンピック 予選(オンライン) | AtCoder
変数の説明
- d←日にち k←服の枚数
- maxi,mini←その日に着れる服の派手さの最大値、最小値
- dp←dpテーブル
- n←何日目かを表す
- previous前日の値を入れる
関数DP内の説明および罠
もしn==dの場合0を返すなので、max[d]とかは関数で用いられないので安心
n==0のとき、最初は一個前との差を比べられないのでpreviousに今の値を入れる
ちなみに、previousに今の値を入れることによって、再帰したとき、n+1となるので前の日の値という風になります
手書きですみません。
いろいろ
まず、dpテーブルに計算し終わる前に代入しないこと
dpというのは、基本全探索だっていうことも頭に入れておきます
割と単純なのかもしれないです、ACできて本当に良かったです