HDU 3006

http://acm.hdu.edu.cn/showproblem.php?pid=3006
集合内の数字が最大で14しかないことに気づいて、状態を圧縮して、それからすべての状態を挙げます

#include <iostream>

#include <cstdio>

#include <cstring>



using namespace std;



int dp[1<<15];



int main() {

    int n, m;

    while(~scanf("%d%d", &n, &m)) {

        memset(dp, 0, sizeof(dp));

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

            int k;

            scanf("%d",&k);

            int s = 0;

            for(int j = 0; j < k; j++) {

                int e;

                scanf("%d", &e); 

                s |= (1<<(e-1));

            }

            dp[s] = 1;

            for(int j = 0; j < (1<<14); j++)

                if(dp[j]) 

                    dp[s|j] = 1;

        }

        int ans = 0;

        for(int i = 0; i < (1<<14); i++)

            if(dp[i]) ans++;

        printf("%d
", ans);

    }

    return 0;

}

View Code