2015广东工业大学ACM学校巡回赛 I 游戏高手 （如压力dp）

Description

Input

Output

Sample Input

Sample Output

HINT

题目链接: http://4.gdutcode.sinaapp.com/problem.php?cid=1021&pid=8

这个题目真的是坑爹，题目读了半个小时

题意：你要收集6张牌，n个朋友。对每个朋友

m num  //m代表你要从这个朋友中拿编号为num的牌仅仅有m中情况，然后列出m中情况

k   //表示这一种情况下你手中必须有k张牌，以下k个数相应的是你手中必须有的k中牌的编号

a a a  .....

c  //代表这个朋友这样的情况下拿编号为num的牌的代价，这3 行为 一个朋友的一种情况，当3*m行结束后是下一个朋友的情况

思路:状压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 long long ll;

#define fre(i,a,b)  for(i = a; i <b; i++)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#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 120

int va[N][7];
int dp[N];
int n,m;

void solve()
{
   int i,j,cur;
   mem(dp,INF);

   dp[0]=0;

   int len=1<<6;

   int le,to;

   fre(cur,0,len)
      fre(i,0,6)
       {
       	   if((cur&(1<<i))) continue;

           if(dp[cur]==INF) continue;

		   le=cur^(1<<i);

		   for(to=0;to<len;to++)
			  if(va[to][i]!=INF&&((cur&to)==to))
				  dp[le]=min(dp[le],dp[cur]+va[to][i]);
       }

	if(dp[len-1]==INF)
		dp[len-1]=-1;

	pf("%d\n",dp[len-1]);

}

int main()
{
   int i,j,t;

   sf(t);

   while(t--)
   {
       mem(va,INF);

       sf(n);

       int m,num,k,x,c;

       fre(i,0,n)
       {
       	  sff(m,num);
       	  while(m--)
		  {
		  	 int te=0;
		  	 sf(k);
		  	 while(k--)
			 {
			 	sf(x);
			 	if(!(te&(1<<x)))   //预计有反复的牌。错了一遍
			 	 te|=(1<<x);

			 }
            sf(c);
            va[te][num]=min(va[te][num],c);   //预计有反复的。取小的
		  }
       }
      solve();
   }
   	  return 0;
}

/*

1
6
1 0
0
1
1 1
0
1
1 2
0

1
1 3
0
1
1 4
0
1

1 5
0
1

*/