本题是一道背包+状态压缩的动态规划题目。
对于经典的背包问题，我们一般会用f[i][j]表示从前i个物品中选出若干个，总重量是j的情况下能达到的最高价值。
对于本题，我们不再关心重量，而是关心“属性”的奇偶性。根据题目描述，一共有m(m <= 10)种属性，所以我们可以用一个[0, 2^m)的整数s表示m种属性每种的奇偶性。
于是类似经典的背包，我们可以用f[i][s]表示从前i个物品中选出若干个，属性奇偶性是s的情况下能达到的最高价值。
假设第i件物品的价值是v[i]，属性奇偶性是st[i]，则 f[i][s] = max(f[i-1][s], max{f[i-1][t] + v[i], 其中t=0, 1, ... 2^m-1 且 t|st[i] == s})
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--) {
int n, m;
cin >> n >> m;
int status = 1 << m; // 所有属性的组合，取或者不取，用二进制表示状态，即状态压缩
static int f[1005][1 << 11]; // 表示从前i个物品中选出若干个，属性奇偶性是s的情况下能达到的最高价值
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
int v, s, st = 0;
cin >> v >> s;
for (int j = 0; j < s; j++) {
int attr;
cin >> attr;
st |= 1 << (attr - 1); // 把每个物品拥有的属性位置值为1，无的为0
}
for (int t = 0; t < status; t++) {
if (!f[i - 1][t]) {
f[i][t | st] = max(f[i - 1][t | st], f[i - 1][t] + v);
}
}
}
cout << max(f[n][status - 1], 0) << endl;
}
return 0;
}
按照题目分析写的，样例过了，提交为0分。。。。。
应该是异或不是或吧
如果t ^ st[i] == s，但f[i-1]不存在 t 这个状态，还是不能转移吧