HUST 1371 Emergency relief

状态压缩。

每一个人所需的物品对应一个数字，统计一个每个数字有几个。每一种提供物品的状态也对应一个数字，然后暴力判断。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 70000;
int n, m, k;
int tot[maxn];
int ans;
int base[40], y;


int main()
{
    
    while (~scanf("%d%d%d", &n, &m, &k)){
        memset(tot, 0, sizeof tot); ans = 0;
        for (int i = 1; i <= k; i++)
        {
            int t; scanf("%d", &t);
            int state = 0;
            for (int j = 1; j <= t; j++)
            {
                int x; scanf("%d", &x); x--;
                state = state + (1 << x);
            }
            tot[state]++;
        }

        for (int i = 0; i <= (1 << n) - 1; i++)
        {
            int tmp = i; y = 0;
            while (tmp) base[y++] = tmp % 2, tmp = tmp / 2;
            int num = 0;
            for (int i = 0; i < y; i++) if (base[i]) num++;
            if (num != m) continue;

            int ans_now = 0;
            for (int j = 0; j <= i; j++)
                if ((j|i)==i) 
                    ans_now = ans_now + tot[j];
            ans = max(ans, ans_now);
        }
        printf("%d
", ans);
    }
    return 0;
}