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
6
HINT
题目链接:?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-8typedef 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 pfprintf#define bugpf("Hi\n")using namespace std;#define INF 0x3f3f3f3f#define N 120int 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;}/*161 0011 1011 2011 3011 4011 501*/
逆境磨练人、逆境是老师、逆境之苦可变甜。
