srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

区間dp

yukicoder No.484 収穫

問題 問題概要 i番目の木はA[i]の実が実る. 時刻1で隣の木にいどうすることができる. 移動しなくてもよい. このような条件ですべての実を回収するのにかかる時間の最小値を求める. 解法 区間dpで解けるみたい. 今回の問題を考えるにあたって重要な考察は, i…