题目链接
题目大意是有n道题，给出每道题的ai、bi和前置要求完成的题目编号，在t时刻完成编号为i的题获得分数为t*ai+bi（可以为负），求每分钟完成一道题且不要求所有题都完成的情况下的最大分数。
虽然第一眼就觉得是状压，也想到状压该怎么转移，但是可能因为状压的题写的太少，感觉限制太多了有环什么的，不自觉就想偏到在拓扑的同时dp，然后脑子一抽写成了暴搜...（全排列的复杂度是真的骚QAQ）
赛后看了聚聚的题解，呃，可以说是非常暴力了。。。
还有一点，亲测这道题的数据并没有环，虽然其实有没有环写起来差不多，但对我这种蒟蒻不太友好。。。
题目解法就是将状态用二进制数表示，二进制形式下如果第i位为1则说明已完成该题，如果没有前置题目的要求，那么直接枚举为1的所有位，代表若该题是已完成的题目中的最后一题，取所有情况的最大值即可。
有了前置题目的要求后，意味着有些状态并不是合法的状态，比如完成1需要先完成2，那么就不会出现完成了1却没有完成2的状态，直接将这些限制建边，枚举状态时遍历状态中完成的题目的所有边，即可判断该状态是否合法，对于合法的状态，就像没有限制的情况下一样转移就好了。
如果本题还有环的话，那么还需要考虑一种情况：如完成1需要先完成2，完成2需要先完成1，形成了环，那么两者应该都完不成，可是在两者都完成了的状态里，按前面的判断方法会被认为是合法的，因此我们需要将dp数组初始化为负无穷，这样这些不存在的状态就不会影响最后的结果了。当然也可以特判一下，只有转移到当前状态的状态的dp值不为负无穷才更新当前状态，也可以确保得到正确答案。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N = 22;
const int mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,a[N],b[N],si;
vector<int> e[N];
bool vis[N];
const int S=1<<20;
ll dp[S],ans=0;
int x;
int main(){memset(dp,-INF,sizeof(dp));dp[0]=0;scanf("%d",&n);For(i,1,n){scanf("%d %d %d",&a[i],&b[i],&si);For(j,1,si){scanf("%d",&x);e[i].push_back(x);}}int s=(1<<n)-1;For(i,1,s){bool flag=0;For(j,1,n){if(((1<<(j-1))&i)==0) continue;For(k,0,(int)e[j].size()-1){if(((1<<(e[j][k]-1))&i)==0){flag=1;break;}}if(flag) break;}if(flag) continue;int tmp=i,tt=0;while(tmp){if(tmp&1) tt++;tmp>>=1;}For(j,1,n){if(((1<<(j-1))&i)==0) continue;if(dp[i-(1<<(j-1))]!=-INF)dp[i]=max(dp[i],dp[i-(1<<(j-1))]+tt*a[j]+b[j]);}ans=max(ans,dp[i]);}printf("%lld\n",ans);return 0;
}时间：15ms