DP

AtCoder

[AtCoder][DP][Educational DP Contest][競プロ]J-Sushi

Educational DP Contest 問題 問題キャプチャ 方針 \(dp\)として、\(i\)は\(a_i = 1\)の個数、\(j\)は\(a_i = 2\)の個数、\(k\)は\(a_...
AtCoder

[AtCoder][DP][競プロ][Educational DP Contest]I-Coins

Educational DP Contest 問題 問題キャプチャ 方針 表の枚数が\(i\)枚である確率をDPとする。こうするとDPテーブルは\(1\)次元で良い。 解答 #atcod...
AtCoder

[AtCoder][競プロ][DP][Educational DP Contest]H-Grid 1

Educational DP Contest 問題 問題キャプチャ。 方針 単純な漸化式で良い。\(H\times W\)のDPを作り、マスが"#"のときは\(dp = 0\)として、マスが"."の...
AtCoder

[AtCoder][競プロ][DP][Educational DP Contest]G-Longest Path

Educational DP Contest 問題 問題キャプチャ。 方針 最初にリストに各点から到達しうる点を収納する。DPとしては、\(dp(i)\)を「頂点\(i\)」から開始するパスで最も長...
AtCoder

[AtCoder][DP][Educational DP Contest]F-LCS

Educational DP Contest 問題 問題キャプチャ。 方針 Longest Common Subsequence (LCS)の問題。 蟻本に従う。長さを求める問題は多い...
AtCoder

[AtCoder][DP][Educational DP Contest][競プロ]E-Knapsack 2

Educational DP Contest 問題 問題キャプチャ。 方針 設定は同じ問題。 上の問題と同じだけど、\(W\)が大きいので、\(NW\)のDPテーブルを作成することはできな...
AtCoder

[AtCoder][DP][Educational DP Contest]D-Knapsack 1

Educational DP Contest 問題 問題キャプチャ。 方針 \(N\)が小さく、\(W\)が大きい。また\(v_i\)も大きいので、計算量が\(O(NW)\)となるようにする。蟻本に...
AtCoder

[AtCoder][DP][Educational DP Contest]C-Vacation

Educational DP Contest 問題 問題キャプチャ。 方針 配列を\(3\)つ作る。 解答 #atcoder template def main(): impor...
AtCoder

[AtCoder][DP][Educational DP Contest]B-Frog 2

Educational DP Contest 問題 問題キャプチャ。 方針 Frog 1の強化版。計算量は\(O(NK)\)かかる。 解答 #input n, k = map(int, ...
タイトルとURLをコピーしました