競プロおぼえがき

おぼえがきのためのブログ

動的計画法(DP)

yukicoder | No.92 逃走経路

問題 No.92 逃走経路 - yukicoder 概要 個の町があり。個の道の情報が渡される。 番目の道の情報 は、で移動できる事を示している。 ここで個の移動コスト履歴が与えられたときに、移動完了後の町の位置としてあり得るものを列挙する。 考え方 の配列を使う…

yukicoder | No.496 ワープクリスタル (給料日前編)

問題 No.496 ワープクリスタル (給料日前編) - yukicoder 概要 座標から与えられた座標まで移動する最小のコストを求める。 移動は徒歩またはワープを使用することができ、ワープを使用する場合は、までコストで移動することができる。 隣の座標に移動する際…

yukicoder | No.527 ナップサック容量問題

問題 No.527 ナップサック容量問題 - yukicoder 概要 ナップサックに入れる荷物の情報と価値の最大値が与えられる。 ナップサックの容量として考えられる最小値と最大値を求める。 ただし最大値が定まらない場合は"inf"を出力する。 考え方 とりあえずは普通…

yukicoder | No.45 回転寿司

No.45 回転寿司 - yukicoderを解きました。 問題概要 N皿の寿司が流れてきてそれぞれのお寿司の美味しさがvである。 一度流れてしまった皿はとることができず、連続で皿をとることもできない。 以上の条件のときの美味しさの合計の最大を求める。 考え方 配…

yukicoder | No.4 おもりと天秤(動的計画法)

No.4 おもりと天秤 - yukicoderを解きました。 問題概要 重りの個数Nと各おもりの重さwが与えられる。 重りを天秤に乗せたときに、左右水平にすることができるか判定する。 考え方 そもそも合計が奇数だったら水平にならないから最初に合計を求める。 合計が…