HDU 3182 Hamburger Magi（状压dp）

1
4 90
243 464 307 298 
79 58 0 72
3 2 3 4
2 1 4
1 1
0

298

思路：状压dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>


#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
typedef __int64 ll;

#define fre(i,a,b)  for(i = a; i <b; i++)
#define free(i,b,a) for(i = b; i >= a;i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define ssf(n)      scanf("%s", n)
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define bug         pf("Hi\n")

using namespace std;

#define INF 0x3f3f3f3f
#define N 1005

int dp[1<<17],ss[1<<16];
int cost[N],va[N];
int n,all,ca[1<<16];

void solve()
{
	int i,j;

	mem(ss,0);

	mem(dp,-1);
	dp[0]=0;

	int len=1<<n;

	int cur;

	fre(cur,0,len)
	{

		if(dp[cur]==-1) continue;

		fre(j,1,n+1)
			{
				if(cur&(1<<(j-1))) continue;

				int to;

				if((cur&ca[j])!=ca[j]) continue;

				to=cur|(1<<(j-1));

				if(dp[cur]+va[j]>dp[to]&&ss[cur]+cost[j]<=all)   //可以更优的到达to，并且花的钱不超过all
				{
					dp[to]=dp[cur]+va[j];
					ss[to]=ss[cur]+cost[j];
				}

			}

	}
	int ans=0;
	fre(cur,0,len)
	   ans=max(ans,dp[cur]);

	pf("%d\n",ans);

}

int main()
{
	int t,i,j;
	sf(t);
	while(t--)
	{
		sff(n,all);

		fre(i,1,n+1)
		  sf(va[i]);

		fre(i,1,n+1)
		  sf(cost[i]);

		mem(ca,0);

		int x,k;


		fre(i,1,n+1)
		{
			sf(k);
			while(k--)
			{
				sf(x);
				ca[i]=ca[i]|(1<<(x-1));
			}
		}

		solve();

	}
   return 0;
}

HDU 3182 Hamburger Magi（状压dp）

原文：http://blog.csdn.net/u014737310/article/details/44619847