首页 > 代码库 > SNNU女装T台走秀(状压dp)

SNNU女装T台走秀(状压dp)

呜啦啦啦啦啦啦~~!!SNNU首届女装T走秀大赛开始了!

本次比赛共有N名队员希望参加比赛;ddjing希望这次比赛尽可能的吸睛,因此他决定对N名队员进行一次海选;

多亏ddjing有一双发现美的眼睛,他发现,每个人都有一个乃至多个的个性,ddjing把这些个性编号为1~M(1<=M<=10);此外,他还发现,每个人都有自己的魅力值Q(1<=Q<=1000)。

ddjing有很严重的强迫症,乃至强迫癌晚期,因此通过这次选拔后,他希望每种个性都只能出现奇数次;在这种前提下,本次女装大赛的出场人员魅力值总和最大是多少?

 

输入

第一行一个数T(1<=T<=50),表示数据组数。对于每一组数据:

第一行两个数N,M(1<=N<=1000,1<=M<=10)

接下来每两行描述一名参赛人员。对于每一名参赛人员:

第一行两个数Q和S,表示其魅力和所含个数数量(1<=Q<=1000,1<=<S<=M)

第二行S个数,表示他拥有的个性编号(1<=编号<=M)

 

输出

输出本次比赛的出场人员魅力总和最大值,不存在则输出-1。

 

样例输入

1

3 2

2 1

1

2 1

2

5 2

1 2

 

样例输出

5

 

 

题解思路:

将每个人的个性压缩成二进制位,通过异或来判断出现次数的奇偶,然后用这个数当成物品的体积,最终状态为2^m -1,这样就可以将问题转化成01背包。

由于是异或背包,所以直接用一维数据有可能导致某些“物品”或者“容量”被重复操作,因此至少需要2个数组来保存上一状态和当前状态,为了不再增加题目代码量,所以不对空间进行限制,可以使用n*2^m 的空间。

背包初始状态bag[0][0]=0,其余为-1,表明该状态目前不可达,也就是说,该状态暂时没有后继。

 

 1 #include<bits/stdc++.h> 2 using namespace std; 3 int t,n,m,bag[1002][1027],q,s;//第二维大于1024即可  4 int main(){ 5     scanf("%d",&t); 6     while(t--){ 7         scanf("%d%d",&n,&m); 8         memset(bag,-1,sizeof bag); 9         bag[0][0]=0;10         int goal=1<<m;11         for(int i=1;i<=n;i++){12             scanf("%d%d",&q,&s);13             int w=0;14             for(int j=0;j<s;j++){15                 int c;16                 scanf("%d",&c);17                 w|=1<<(c-1);//因为序号是从1开始的 18             }19             for(int j=0;j<goal;j++){20                 if(bag[i-1][j]==-1) continue;21                 bag[i][j^w]=max(bag[i][j^w],bag[i-1][j]+q);22                 bag[i][j]=max(bag[i][j],bag[i-1][j]);23             }24         }25         printf("%d",bag[n][goal-1]);26     }27     return 0;28 } 

 

SNNU女装T台走秀(状压dp)