ある区間から遷移する問題． 貰うDPなら累積和（ある区間からの遷移），配るDPならいもす法（ある区間への遷移）となる．個人的には，いもす法の方がわかりやすい． 方法1 (貰うDP & 累積和) 考え方 回答例 方法2 (配るDP & いもす法) 考え方 回答例 背景 方…

【類題】EDPC - D - Knapsack 1 - 競プロはじめました 考え方 DP - 「ぴったり」で考える方法 貰うDP 考え方まず，制約から何を変数に使えるか考える．D - Knapsack 1とは，制約のみ異なる．これにより，変数に$W$を使うことはできなくなる．代わりに，$v_{i…

【類題】EDPC - E - Knapsack 2 - 競プロはじめました 考え方②：「ぴったり」で考える方法 貰うDP 考え方①：「以下」で考える方法 貰うDP 考え方②：「ぴったり」で考える方法「$W$以下」ではなく，「$W$ぴったり」となるように考えるのがよくあるパターン．…