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

ferinの競プロ帳

競プロについてのメモ

AOJ

AOJ 1161 ダルマ落とし

Daruma Otoshi | Aizu Online Judgedp[l][r] = {lからrまでの区間の状態}と持ってDPする、区間DPの問題。 この問題ではdp[l][r] = {lからrまでの区間で叩ける最大のブロック数}とする。 dp[l+1][r-1]の区間が全てのブロックを叩き出すことができ、l番目とr番…

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 となります。さらに…