AtCoder [AtCoder][DP][Educational DP Contest][競プロ]J-Sushi
Educational DP Contest
問題
問題キャプチャ
方針
\(dp\)として、\(i\)は\(a_i = 1\)の個数、\(j\)は\(a_i = 2\)の個数、\(k\)は\(a_...
Educational DP Contest
AtCoder 
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]B-Frog 2
Educational DP Contest
問題
問題キャプチャ。
方針
Frog 1の強化版。計算量は\(O(NK)\)かかる。
解答
#input
n, k = map(int, ...
AtCoder [AtCoder][DP][Educational DP contest]A-Frog 1
Educational EP Contest
問題
問題キャプチャ。
方針
\(1\)次元のDPで。初期化はinfじゃなくても\(0\)で大丈夫。\(O(N)\)。
解答
#atcode...