https://codeforces.com/problemset/problem/417/D

题意:

一共需要解决m道问题。 每个人需要x元的费用， 又需要y台监视器才答应写题目，每台b元。给出每个人可以解决的题目。

求最少需要多少花费能够解决所有问题。

题解

状态压缩DP。把每个人可以解决的题目集合状态压缩一下。

按需要监视器数量从小到大 排序, 以便顺序扫描。

枚举到第i个人，那么编号≤i的人都满足监视器的要求。监视器的费用可以单独考虑。不用dp。

dp[S]表示解决集合S内所有题目的最小花费，S为一个整数。

初始化为-1，dp[0] = 0。

 状态转移( 假设dp[j]已经知道)：

dp[j|p[i].s] = min(dp[j|p[i].s],dp[j] + p[i].x);

集合{a,b,c}的所有子集合为：

{a}, {b}, {c},{a,b},{a,c},{b,c},{a,b,c}

对应的二进制数：

1，10，100， 11，101，110，111

如果集合的大小n<32,可以考虑使用状态压缩，

即用一个数i<(1<<n)表示一个子集合。