对于0~k，我们分i到j的最短路正好经过顶点k一次和完全不经过顶点k两种情况来讨论。

BUPT2017 wintertraining(15) #4E Gym - 101138K

给你n（1 ≤ n ≤ 106）个数a1..an（0 ≤ ai ≤ 109），再给你m（ 2 ≤ m ≤ 103）如果n个数的子集的和可以被m整除，则输出YES，否则NO。

题意：给你n种价值不同的邮票，最大的不超过10000元，一次最多贴k张，求1到多少都能被表示出来？n≤50，k≤200。

状态转移：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]，即第i位放1或者0。

N (1 <= N <= 39),问有多少种把1到N划分为两个集合的方法使得两个集合的和相等。

dp[i][j]=dp[lk][ln]*dp[rk][j-1-ln]，max(lk,rk)=i-1。

dp[i][j]表示前i种货币价格为j有多少种方案，dp[i][j]+=dp[i-1][j-c]。

完全背包的特点恰是每种物品可选无限件，所以就可以并且必须采用 w = W[i]…carry 的顺序循环：

Problem Description Phoenix is picking berries in his backyard. There are n shrubs, and each shrub has ai red berries and bi blue berries.