传送门：E题.AC Challenge
题意：有 n 个问题（0<n≤20 ），解决一个问题花费 1 分钟，但解决问题 i 时，必须已经解决问题p1,p2, ... ,psi（记为问题 i 的前驱问题）。当问题 i 是你解决的第 t 个问题（在第 t 分钟）时，总分加上 ai*t+bi。求总分的最大值。
题解：考虑到n较小，可以采取状态压缩来表示问题的状态。例如，二进制数0100表示第3个已解决。
求总分的最大值，考虑状压dp来解决。dp[i]表示状态为i时的最高得分，则状态转移方程为 dp[i]=max(dp[i],dp[tmp]+(ll)(t+1)*a[j]+b[j]); //tmp=i-(1<<(j-1)); 问题j的上一个状态
预处理：把问题 x的前驱问题的状态存到pre[x]中。
状态转移条件：
1.i状态下第j个问题已解决；
2.定义tmp为前驱状态，与i相比，tmp中只相差一个j问题；
3.tmp状态下的前驱问题已解决，即tmp&pre[i]==pre[i]；
4.dp[tmp]处于合法状态。
从大到小，枚举所有状态。内部枚举每一个问题，满足条件的话，进行状态转移。
代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN (1<<20)+5
#define ll long long
ll pre[25],dp[MAXN],a[25],b[25];
int n,s,p;
int main()
{while(~scanf("%d",&n)){memset(pre,0,sizeof(pre));for(int i=1;i<=n;i++){scanf("%lld%lld%d",&a[i],&b[i],&s);while(s--){scanf("%d",&p);pre[i]+=1<<(p-1);}}dp[0]=0;int m=(1<<n)-1;ll ans=0;for(int i=1;i<=m;i++){dp[i]=-inf; //初始化for(int j=1;j<=n;j++){if(i&(1<<(j-1))){int tmp=i-(1<<(j-1)); //前驱状态if(dp[tmp]==-inf) continue; //前驱状态处于不合法状态if((tmp&pre[j])==pre[j]){int num=0;for(int k=0;k<n;k++){if(tmp&(1<<k)){num++; //前驱问题解决的时候所消耗的时间}}dp[i]=max(dp[i],dp[tmp]+(ll)(num+1)*a[j]+b[j]);//printf("dp[%d]=%d\n",i,dp[i]);ans=max(ans,dp[i]);}}}}printf("%lld\n",ans);}return 0;