2018南京站网络赛 E AC Challenge 状压DP

题目链接：https://nanti.jisuanke.com/t/A1951
题目大意：有n道题，分别有a[i]和b[i]属性。如果你在时间T去做它。那么你得到的分数是T*a[i]+b[i]。而且它有s个前置题目。你必须把这些题写完才能写这题。(0<n<=20, |a[i], b[i]|<=1e9)问能得到最大分数。

思路：状压DP：f[s]：写完s集合的最大分数。开始写复杂了。s集合是否是一个可能的集合。我预处理了g[i]：写i题时，前面必须写完的题目。然后每个s判断了一下已经存在的点。再判断要下个要转移的点。
比较简洁的思路：我们只要预处理了g[i]：i前置的题，和上面的不同例如1->2 2->3。这个g[3]=010.上面是g[i]=011。然后把f设置无穷小。f[0]=0。只要判断转移的点是否合法就可以了。因为前面不是合法状态，转移是无穷小。如果是合法。那么s中那些点的所有前置状态都满足了。我们这个满足就可以加进去了。

#include <bits/stdc++.h>
using namespace std;
#define  LL long long

int a[25], b[25], num[1<<21], g[21];
LL f[1<<21], ans=0;
int main(){
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d%d", &a[i], &b[i]);
        int siz, u; scanf("%d", &siz);
        while(siz--){
            scanf("%d", &u); u--;
            g[i]|=(1<<u);
        }
    }
    for(int i=1; i<(1<<21); i++){
        num[i]=num[i>>1]+i%2;
    }
    memset(f, 0x80, sizeof(f));
    f[0]=0;
    for(int s=0; s<(1<<n); s++){
        for(int i=0; i<=n; i++){
            if(!(s&(1<<i))&&(g[i]&s)==g[i]){
                f[s^(1<<i)]=max(f[s^(1<<i)], f[s]+1ll*num[s^(1<<i)]*a[i]+b[i]);
                ans=max(ans, f[s^(1<<i)]);
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}