hiho一下 第244周 A 物品价值 状压DP

题目1 : 物品价值

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi现在有n个物品，每个物品都有一个价值。并且这n个物品总共有m个不同的属性，每个物品都具有其中若干属性。

小Ho要从中选出若干物品，满足每个属性都正好有奇数个物品拥有，且被选出的物品价值总和最大。你能帮助小Ho完成任务么？

输入

第一行一个数T(<=10)，表示数据组数。对于每一组数据：

第一行两个数n，m（1<=n<=1000，m<=10）

接下来每两行描述一件物品。对于每一件物品：

第一行两个数v和s，表示其价值和所含属性数量(v<=100000,s<=m)

第二行s个数，表示该物品拥有的属性编号(1<=编号<=m)

输出

物品价值总和的最大值。

样例输入

1
3 2
2 1
1
2 1
2
5 2
1 2

样例输出

5

dp[i][j]前i个，状态为j的最大值

偶数为0奇数为1

1<<10

#include<bits/stdc++.h>
using namespace std;
int dp[1005][2300];
void init()
{
    memset(dp,0,sizeof(dp));
}
void getans(int m)
{
    int nas=0;
    for(int i=0; i<1005; i++)
        nas=max(nas,dp[i][(1<<m)-1]);
    printf("%d\n",nas);
}
int main()
{

    int t;
    cin>>t;
    while(t--)
    {
        init();
        int v,s,m,n;
        int x;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&v,&s);
            int u=0;
            for(int j=1; j<=s; j++)
            {
                scanf("%d",&x);
                u^=(1<<(x-1));
            }
            for(int j=0; j<(1<<m); j++)
            {
                if(dp[i-1][j^u]>0||(j^u)==0)
                    dp[i][j]=max(dp[i-1][j^u]+v,dp[i][j]);
                dp[i][j]=max(dp[i-1][j],dp[i][j]);
            }
        }
        getans(m);
    }
    return 0;
}