ACM-ICPC2018南京网络赛 AC Challenge（一维状压dp）

AC Challenge

30.04%
1000ms
128536K

Dlsj is competing in a contest with

However, he can submit $s_isi problems, the p_{i, 1}pi,1-th, p_{i, 2}pi,2-th, ......, p_{i, s_i}pi,si-th problem before.(0 < p_{i, j} le n,0 < j le s_i,0 < i le n)(0<pi,j≤n,0<j≤si,0<i≤n) After the submit of a problem, he has to wait for one minute, or cooling down time to submit another problem. As soon as the cooling down phase ended, he will submit his solution (and get "Accepted" of course) for the next problem he selected to solve or he will say that the contest is too easy and leave the arena.$

"I wonder if I can leave the contest arena when the problems are too easy for me."
"No problem."
—— CCF NOI Problem set

If he submits and passes the $a_i + b_it×ai+bi points. (|a_i|, |b_i| le 10^9)(∣ai∣,∣bi∣≤109).$

Your task is to calculate the maximum number of points he can get in the contest.

Input

The first line of input contains an integer,

Then follows $s_i + 3si+3 integers, a_i,b_i,s_i,p_1,p_2,...,p_{s_i}ai,bi,si,p1,p2,...,psias described in the description above.$

Output

Output one line with one integer, the maximum number of points he can get in the contest.

Hint

In the first sample.

On the first minute, Dlsj submitted the first problem, and get

On the second minute, Dlsj submitted the second problem, and get

On the third minute, Dlsj submitted the third problem, and get

On the forth minute, Dlsj submitted the forth problem, and get

On the fifth minute, Dlsj submitted the fifth problem, and get

So he can get

In the second sample, you should note that he doesn't have to solve all the problems.

样例输入1

样例输出1

样例输入2

1
-100 0 0

样例输出2

题目来源

ACM-ICPC 2018 南京赛区网络预赛

状压dp。

#include <bits/stdc++.h>
#define MAX 21
typedef long long ll;
using namespace std;
const int INF = 0x3f3f3f3f;

ll a[MAX],b[MAX];
ll dp[1<<20];
vector<int> v[MAX];

int main(void)
{
    int n,num,temp,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++) {
        scanf("%lld %lld",&a[i],&b[i]);
        scanf("%d",&num);
        while(num--) {
            scanf("%d",&temp);
            v[i].push_back(temp);
        }
    }
    memset(dp,0,sizeof(dp));
    for(i=0;i<(1<<n);i++){
        int f=0;
        for(j=1;j<=n;j++){
            if(!((1<<(j-1))&i)) continue;
            for(k=0;k<v[j].size();k++){
                if(!((1<<(v[j][k]-1))&i)){
                    f=1;
                    break;
                }
            }
            if(f==1) break;
        }
        if(f==1) continue;
        for(j=1;j<=n;j++){
            if(!((1<<(j-1))&i)) continue;
            int S=i;
            int c=0;
            while(S){
                if(S&1) c++;
                S>>=1;
            }
            dp[i]=max(dp[i],dp[i^(1<<(j-1))]+c*a[j]+b[j]);
            //printf("(%d %d %d %lld)",i,c,j,dp[i]);
        }
    }
    printf("%lld
",dp[(1<<n)-1]);
    return 0;
}