本文主要是介绍ACM-ICPC 2018 南京赛区网络预赛 E AC Challenge(状压DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://nanti.jisuanke.com/t/30994
题目大意：有n道题，每道题做出来会得到t*a[i]+b[i]分，但是有些题目有先决条件，需要先完成某些题目才能写，问最多能得到多少分
题目思路：这道题需要用二进制的做法。首先先用二进制表示每道题的先决条件，放入pre数组，第几位是1就是需要先写第几题。然后就把所有的情况全部枚举出来，由于一共就20题，一共也就2^20的情况，然后也是用二进制表示每一种情况。由于是从小到大，所以他的前一刻一定都已经出来了，然后就试探把每一位删掉，判断这道题需要做的先决条件是否已经够了，先&pre[i]，如果能够等于pre[i]，这说明需要的题目都已经出了，可以推出当前情况，然后数出这种情况是第几个1，也就是说这道题是哪一刻做的，然后就可以算出这种情况下的值。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN (1<<20)+5
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
ll pre[25],dp[MAXN],a[25],b[25];
int n,m,x;
int main()
{while(~scanf("%d",&n)){memset(pre,0,sizeof(pre));rep(i,1,(1<<n)-1)dp[i]=-1e18;rep(i,0,n-1){scanf("%lld%lld%d",&a[i],&b[i],&m);rep(j,0,m-1){scanf("%d",&x);pre[i]+=1<<(x-1);}}ll ans=0;rep(i,1,(1<<n)-1){rep(j,0,n-1){if(i&(1<<j)){int temp=i-(1<<j);if((temp&pre[j])==pre[j]){int num=1;rep(k,0,21){if(temp&(1<<k)){num++;}}dp[i]=max(dp[i],dp[temp]+(ll)num*a[j]+b[j]);ans=max(ans,dp[i]);}}}}printf("%lld\n",ans);}return 0;
}
这篇关于ACM-ICPC 2018 南京赛区网络预赛 E AC Challenge(状压DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
