RCC 2014 Warmup (Div. 2)Cunning Gena_html/css_WEB-ITnose

Question link

Question meaning:
Enter n: number of people, m: number of questions, b: price per monitor
Then for each person, Enter x: the money needed, k the minimum number of monitors required, m: the topic of the meeting
Enter the topic of the meeting on the next line
Select some people so that all the topics are included and the money is the least (the money required by each person (plus monitor money)
(1?≤?n?≤?100; 1?≤?m?≤?20; 1?≤?b?≤?109), (1?≤?xi?≤? 109; 1?≤?ki?≤?109; 1?≤?mi?≤?m)

Analysis:
If the amount of data in the question is relatively small, it is obviously possible to use the state What you can do by pressing DP is to add the status of the currently used monitor. But the key point is that k in the question is relatively large, so if this dimension is added, DP will obviously not be possible. Then we can try to convert it. Since it basically complies with the principles of DP and only the number of monitors is inconsistent, then let's consider how to deal with this state. This state requirement is at least, then if we consider the maximum value of k of all people selected at a certain moment, the other people do not need to consider the k value, because the last k is the maximum. Then there is a direction. You can sort all people by k. For people 0 - i-1, it is a normal DP (k is not considered, only the question is considered). When it comes to the i-th person, find those states that can be compared with i The total of human questions reaches all values ​​(covering all questions), but at this time k*percost can be added.
Again, this problem can actually be considered as DLX, with each person as a row and the topic as a column. But the problem is that both the minimum cost and k must be calculated, which is still a repeated coverage. The pruning efficiency is not high, and it will time out for this amount of data, but it is also a direction.

Key points:
The key is to deal with a large dimension, so that the problem can be solved using state pressure DP
Pay attention to the initialization of 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;}