题目链接：https://nanti.jisuanke.com/t/30994
样例输入：
5
5 6 0
4 5 1 1
3 4 1 2
2 3 1 3
1 2 1 4
样例输出：
55
样例输入：
1
-100 0 0
样例输出：
0
题解：
把n道题目做了或者没做作为状态，裸的状压DP。
其中当前的时间 t，就是当前做了的题目数量加上1。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18; const int maxn=; int n;
struct P{
ll a,b;
int pre;
}p[maxn]; ll dp[<<maxn]; int main()
{
cin>>n;
for(int i=,s;i<=n;i++)
{
scanf("%lld%lld",&p[i].a,&p[i].b); scanf("%d",&s);
p[i].pre=;
for(int j=,o;j<=s;j++)
{
scanf("%d",&o);
p[i].pre=p[i].pre|(<<(o-));
}
}
//for(int i=1;i<=n;i++) printf("%lld %lld %d\n",p[i].a,p[i].b,p[i].pre); for(int sta=;sta<(<<n);sta++) dp[sta]=-INF;
dp[]=; ll ans=;
for(int sta=;sta<(<<n);sta++)
{
if(dp[sta]==-INF) continue; ll t=;
for(int i=;i<=n;i++) if(sta&(<<(i-))) t++; for(int i=;i<=n;i++)
{
if(sta&(<<(i-))) continue; if(p[i].pre== || (p[i].pre&sta)>=p[i].pre)
{
int nxt=sta|(<<(i-));
dp[nxt]=max(dp[nxt],dp[sta]+t*p[i].a+p[i].b);
ans=max(dp[nxt],ans);
}
}
} cout<<ans<<endl;
}
时间复杂度 $O\left( {2^n \cdot n} \right)$，n = 20 时为2e7，1s足够。