読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

AOJ2254 Fastest Route

Fastest Route | Aizu Online JudgeまずNdp[S] = (集合Sをクリアするのにかかる最短時間)とする。 dp[S]は集合Sから要素を一つ取り除いた集合をクリアするのにかかる最短時間 + 集合から取り除いたステージをクリアするのにかかる最短時間と考えられるので…

AOJ 0043-Puzzle

パズル | Aizu Online JudgeDFSで面子と雀頭の取り方を全て試す。

DPL_4 B Coin Combination Problem II

Coin Combination Problem II | Aizu Online JudgeN

DPL_1 E Edit Distance (Levenshtein Distance)

dp[i][j] = (s1のi文字目まででs2のj文字目までを作る最小コスト) としてDPします。 各文字列に対する操作についてDPの遷移を考えると 挿入 dp[i][j] = dp[i][j-1] + 1 削除 dp[i][j] = dp[i-1][j] + 1 置換 dp[i][j] = dp[i-1][j-1] + 1 となります。さらに…