競技プログラミング用 知識集積所

B - Frog 2

最終更新:

sport_programming

- view
管理者のみ編集可


問題


必要知識

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

考え方

前問と考え方自体はほぼ同じ。
「2通りのうち小さい方」が「最大k通りの中での最小」に変更となるだけ。
問題は、もらうDPでも配るDPでも、実装方法を少し考えないといけない点。

もらうDPの場合、前問では最初の2つを特別扱いしていた。
しかし、特別扱いする個数がk個と不確定になってはそうもいかない。
そのため、ループの範囲をmax(未作成)関数などを使って工夫することになる。

配るDPの場合、後ろに大量のダミー足場を付けるなら、いくつ付ければ足りるのか考えなければならない。
また、(今回は影響がないが)メモリや計算時間も確認が必要になる。
あるいは、ダミー足場を用意せずにループをきっちり止める実装だとしても、止め方を考えなければならない。

いずれにせよ二重ループ(未作成)を書くことになるし、範囲外アクセスの慎重な対応が必要で、実装はちょっと大変。

解答例

解答例(もらうDP)
解答例(配るDP/ループをきっちり止める場合)

注意点


別解

タグ:

動的計画法
ウィキ募集バナー