JOI 2010 本選 3 つらら
え？私覚醒した？
†DP†で通しました。
解法書きまーす
問題概要
- N本つららが並んでいます
- 両脇のつららよりながければ、1cm/hで伸びる
- Lまで行くと折れる
- さて全部折れるまで何時間？
-
https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf
解法
両脇が折れる時間+L-今見てるところの長さでその見てるところの長さは出せる
じゃあどうするか。再帰っぽい。
あれ？DPじゃね？
空からDP解法が降ってきた。
両脇より高ければ L-A[i]でreturn
どっちも高かったら低い方だけ見ればいい
どっちかだけ高かったら高い方だけみればいい
みたいなことやって全探索したら幸せになれました
DP解、つらい。
でもなんかできて嬉しかった。
プライオリティーキュー解もあるのでそっちも考えてみるといいかもです
