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

題意:

一共需要解決m道問題。 每個人需要x元的費用， 又需要y臺監(jiān)視器才答應(yīng)寫題目，每臺b元。給出每個人可以解決的題目。

求最少需要多少花費能夠解決所有問題。

題解

狀態(tài)壓縮DP。把每個人可以解決的題目集合狀態(tài)壓縮一下。

按需要監(jiān)視器數(shù)量從小到大 排序, 以便順序掃描。

枚舉到第i個人，那么編號≤i的人都滿足監(jiān)視器的要求。監(jiān)視器的費用可以單獨考慮。不用dp。

dp[S]表示解決集合S內(nèi)所有題目的最小花費，S為一個整數(shù)。

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

?狀態(tài)轉(zhuǎn)移( 假設(shè)dp[j]已經(jīng)知道)：

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

?

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

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

對應(yīng)的二進(jìn)制數(shù)：

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

如果集合的大小n<32,可以考慮使用狀態(tài)壓縮，

即用一個數(shù)i<(1<<n)表示一個子集合。