题意: 一个人有m元钱 有n个汉堡 每个汉堡有其价值和其花费 且做某个汉堡需要做好一些前提汉堡 求最大价值
强行状压即可 把两个&写成了&& QAQ
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=20; int n,m; int cost[N]; int val[N]; int bef[N][N]; int money[N<<15]; int dp[N<<15]; bool judge(int state,int j) { if(state& (1<<(j-1)) )return 0; rep(i,1,bef[j][0]) { int x=bef[j][i]; if( !(state&(1<<(x-1))) )return 0; } return 1; } int main() { int cas;RI(cas); while(cas--) { RII(n,m); rep(i,1,n)RI(val[i]); rep(i,1,n)RI(cost[i]); rep(i,1,n) { int q;RI(bef[i][0]); rep(j,1,bef[i][0]) RI(bef[i][j]); } CLR(dp,-0x3f); CLR(money,0); dp[0]=0; int maxx=0; rep(i,0, (1<<n)-1 ) { rep(j,1,n) if(judge(i,j)&&cost[j]+money[i]<=m&&dp[i]+val[j]>dp[i|(1<<(j-1))] ) { dp[i|(1<<(j-1))]=dp[i]+val[j]; maxx=max(maxx,dp[i|(1<<(j-1))]); money[i|(1<<(j-1))]=cost[j]+money[i]; } } cout<<maxx<<endl; } return 0; }