BZOJ2073 - Click Here
Description
一只队伍在爬山时碰到了雪崩，他们在逃跑时遇到了一座桥，他们要尽快的过桥。桥已经很旧了， 所以它不能承受太重的东西。任何时候队伍在桥上的人都不能超过一定的限制。所以这只队伍过桥时只能分批过，当一组全部过去时，下一组才能接着过。队伍里每个人过桥都需要特定的时间，当一批队员过桥时时间应该算走得最慢的那一个，每个人也有特定的重量，我们想知道如何分批过桥能使总时间最少。
Input
第一行两个数：w – 桥能承受的最大重量(100 <= w <= 400)和n – 队员总数(1 <= n <= 16)。接下来n 行每行两个数分别表示：t – 该队员过桥所需时间(1 <= t <= 50)和w – 该队员的重量(10 <= w <= 100)。
Output
输出一个数表示最少的过桥时间。
Solutions
很显然的一个状压DP。
设$f[S]$表示集合为$S$的最优答案，则转移方程为$f[S]=f[S-S’]+cost,S’\subseteq S$
时间复杂度$O(3^N)$
下面是时间复杂度的分析以及求子集的技巧。
时间复杂度：
由于需要枚举子集，因此时间为$\sum_{i=0}^n C_n^i \times 2^i$。该式等价于$\sum_{i=0}^nC_n^i \times 2^i \times 1^{n-i}$。利用二项式定理得$\sum_{i=0}^nC_n^i \times 2^i \times 1^{n-i}=3^n$。
求子集的技巧：
1 | for (int S = i ; S > 0 ; S = (S - 1) & i) |
其中$i$是全集。至于正确性，自行YY即可。
CODE
CODE - Click Here