C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

動的計画法

いろいろなDP|動的計画法|ナップザック

DP 配列を- INF で埋めた DP が解らなかったのでナップザック問題を使って比較してみました。使う問題はこれ:ナップザック問題 | 動的計画法 | Aizu Online Judge ① 普通に普通の 埋めDP まずは普通に本 *1 で学習したナップザックで解きます。 定義 dp[ i …

ABC015 D - 高橋くんの苦悩|AtCoder

D - 高橋くんの苦悩 を解きました。 題意 この問題は良くある knapsack 問題に置き換えて考えられる為、本当の題意は省略します。 与えられる変数と値は以下のように置き換えて考えます。 … knapsack の容量 … 与えられる荷物の数 … knapsack に詰めれる荷物…

Max値取得|動的計画法( DP )

動的計画法 ( DP )の学習として解きました。 例題のねらい:動的計画法におけるメモ配列とDPテーブルの違いを確認する。問題: 要素の int 型配列 が与えられる. の最大値を DP で求めよ問題制約は特になかったので、適当に。( くらい?) 1. メモ化再帰編 …

No.7 プライムナンバーゲーム|yukicoder|メモ化再帰

No.7 プライムナンバーゲーム - yukicoder を 1ヶ月半 かけて解きました。 (何故 1ヶ月かかったのかは後述) 題意: ・はじめに先攻プレイヤーに自然数 N が与えられます。 ・N以下の素数のどれかで減算し相手に渡す、を先攻・後攻で交互に繰り返し、 N が 0 …