RCC 2014 Warmup (Div. 2)__Cunning Gena - c++编程基础

题目链接

题意：
输入n：人数，m：题目数，b：每个显示器价格
然后对于每个人，输入x：需要的钱，k至少需要的显示器个数，m：会的题目
下一行输入会的题目
选一些人，使得包括所有的题目且钱最少（每个人需要的钱加上显示器的钱）
(1 ≤ n ≤ 100; 1 ≤ m ≤ 20; 1 ≤ b ≤ 109)、 (1 ≤ xi ≤ 109; 1 ≤ ki ≤ 109; 1 ≤ mi ≤ m)
分析：

如果题目中的数据量比较小，显然是可以用状压DP来做的，就是加一个当前用的显示器的状态即可。但是关键在于，题目中的k是比较大的，所以如果把这一维加上去显然是不能进行DP的。那么我们可以尝试着进行转化，既然基本符合DP的原则，只有显示器数量这一个状态是不符合的，那么就考虑一下如何处理这一个状态。这个状态要求是至少，那么我们如果考虑某一时刻所选择的所有人的k的最大值时，其他的那些人是不用考虑k值的，因为最后一个的k是最大的。那么就有方向了，可以将所有的人安装k排序，对于0 - i-1的人是正常的DP（不考虑k，只考虑题目），到第i个人时，找一下那些状态可以和i人的题目加起来达到所有值（覆盖所有题目），不过这时候加上k*percost即可。
再说一下，这个问题其实也可以考虑成DLX，每一个人作为行，题目作为列。但是问题在于，既要最小费用又要计算k，还是一个重复覆盖，剪枝效率不高，对于这个数据量会超时，不过也是一个方向。重点：
关键在于对于大的一个维度的处理，使得问题可以用状压DP来解
注意对INF的初始化

const LL INF = 1100000000000000000;
const int MAXN = 110;

struct Node
{
    int cost, Min, n;
    int operator< (const Node& a) const
    {
        return Min < a.Min;
    }
} ipt[MAXN];

LL dp[1100000];

int main()
{
//    freopen("in.txt", "r", stdin);
    int people, problem, percost;
    while (~RIII(people, problem, percost))
    {
        int all = (1 << problem) - 1;
        FE(i, 1, all) dp[i] = INF;
        dp[0] = 0;
        REP(i, people)
        {
            RII(ipt[i].cost, ipt[i].Min);
            int n, t, v = 0;
            RI(n);
            REP(j, n)
            {
                RI(t);
                v |= (1 << (t - 1));
            }
            ipt[i].n = v;
        }
        sort(ipt, ipt + people);
        LL ans = INF;
        REP(i, people)
        {
            FE(j, 0, all)
            {
                if ((ipt[i].n | j) == all)
                {
                    ans = min(ans, dp[j] + ipt[i].cost + (LL)percost * ipt[i].Min);
                }
            }
            FED(j, all, 0)
            {
                int nxt = j | ipt[i].n;
                dp[nxt] = min(dp[nxt], dp[j] + ipt[i].cost);
            }
        }
        if (ans != INF)
            cout << ans << endl;
        else
            puts("-1");
    }
    return 0;
}