题意：

有n道题，有$a_i$和$b_i$两个值，每道题得在m道题做完之后才能做，给出了这m道题。如果第t个做出这道题目的话，得到的价值为$a_i*t+b_i$。问最大价值为多少。其中$0<n≤20$。

思路：

可以看出来是一道状压dp。

可是我想到了这可以画出一张图然后就走上了一条不归路…比赛的时候连二维还是一维都没有考虑好…还想好难转移…真的智障啊…

怎么就不能好好思考一下呢…

很明显这一维就够了，顺序的不同造成的结果不同就更新dp就好了。

转移也就很明显了，根据题目给的先决条件位运算判断一下是否合法就好了。

比赛的时候真的不在状态啊…可能最近太颓废了…

难受…

代码：

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
ll a[25],b[25];
int pre[25];
ll dp[1100000];
int main()
{
    int n,m,x;
    scanf("%d",&n);
    for(int i=0;i<(1<<n);i++)
        dp[i]=-INF;
    for(int i=0;i<n;i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
        scanf("%d",&m);
        if(m==0)dp[1<<i]=a[i]+b[i];
        pre[i]=0;
        while(m--)
        {
            scanf("%d",&x);
            x--;
            pre[i]+=1<<x;
        }
    }
    /*for(int i=0;i<n;i++)
        printf("pre[%d]=%d\n",i,pre[i]);*/
    ll ans=0;
    dp[0]=0;
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i>>j&1)
            {
                int temp=i-(1<<j);
                if((temp&pre[j])==pre[j])
                {
                    int cnt=__builtin_popcount(temp);
                    //printf("i=%d temp=%d cnt=%d\n",i,temp,cnt);
                    dp[i]=max(dp[i],dp[temp]+a[j]*(cnt+1)+b[j]);
                    //printf("dp[%d]=%lld\n",i,dp[i]);
                    ans=max(ans,dp[i]);
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}