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

2022-12-10 15:07:01

Problem I: 游戏王

Description

小学的时候，Stubird很喜欢玩游戏王。有一天，他发现了一个绝佳的连锁组合，这个连锁组合须要6张卡。但是他一张都没有，但是他的那些朋友们有。只是当然。他们不会白给，只是也不排除有人和他交情好，送给他了。只是他们有成全别人的美德，当他们看到Stubird已经有某些他们喜欢的卡的时候。他们会给他优惠，或者更贵也说不定嘛只是，你能够把有的卡片藏起来，不告诉他们，来获得更低的价格。

问他最少须要多少钱才干够集齐全部的卡。

Input

第一行T，表示有T个測试例子第二行，n表示他有n个朋友(n<=100) 下一行，m(0<=m<=2的6次方)表示有多少种卡片的集合，num表示他有的这张卡片的编号是(0-5)。数据保证所给的集合不反复； 3*m行。第一行都有一个数。k（k<=5）。表示这个集合包括的卡片张数下一行k个数。表示每张卡片的编号（0-5）（不会包括num）下一行一个数c，表示假设你有这个组合下购买num卡。所须要的花费c；

Output

输出最小的花费。假设不可能集齐则输出-1

Sample Input

161 00 11 10 11 20 11 30 11 40 11 50 1

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

*/

码农公寓