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。

样例输入

3 2

2 1

5 2

1 2

样例输出

题解思路：

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

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

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

 #include<bits/stdc++.h>

 using namespace std;

 int t,n,m,bag[][],q,s;//第二维大于1024即可

 int main(){

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&m);

         memset(bag,-,sizeof bag);

         bag[][]=;

         int goal=<<m;

         for(int i=;i<=n;i++){

             scanf("%d%d",&q,&s);

             int w=;

             for(int j=;j<s;j++){

                 int c;

                 scanf("%d",&c);

                 w|=<<(c-);//因为序号是从1开始的

             }

             for(int j=;j<goal;j++){

                 if(bag[i-][j]==-) continue;

                 bag[i][j^w]=max(bag[i][j^w],bag[i-][j]+q);

                 bag[i][j]=max(bag[i][j],bag[i-][j]);

             }

         }

         printf("%d",bag[n][goal-]);

     }

     return ;

 }

巴特西

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

最新文章

热门文章