首页 > ACM题库 > HDU-杭电 > HDU 3006-The Number of set-动态规划-[解题报告]HOJ
2014
02-27

HDU 3006-The Number of set-动态规划-[解题报告]HOJ

The Number of set

问题描述 :

Given you n sets.All positive integers in sets are not less than 1 and not greater than m.If use these sets to combinate the new set,how many different new set you can get.The given sets can not be broken.

输入:

There are several cases.For each case,the first line contains two positive integer n and m(1<=n<=100,1<=m<=14).Then the following n lines describe the n sets.These lines each contains k+1 positive integer,the first which is k,then k integers are given. The input is end by EOF.

输出:

There are several cases.For each case,the first line contains two positive integer n and m(1<=n<=100,1<=m<=14).Then the following n lines describe the n sets.These lines each contains k+1 positive integer,the first which is k,then k integers are given. The input is end by EOF.

样例输入:

4 4
1 1
1 2
1 3
1 4
2 4
3 1 2 3
4 1 2 3 4

样例输出:

15
2

#include <iostream>
#include <cstring>

using namespace std;


int main()
{
    int m,n,k,a;
    int s[1<<15];            //2的15次方
    while(cin>>n>>m)
    {
        int ans=0;
        memset(s,0,sizeof(s));
        while(n--)
        {
            int set=0;
            cin>>k;
            while(k--)
            {
                cin>>a;
                set=set|(1<<(a-1));
            }
            s[set]=1;
            for(int j=0;j<=(1<<14);j++)
            {
                if(s[j])  s[set|j]=1;
            }

        }
        for(int i=0;i<=1<<14;i++)
        {
            if(s[i])
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

参考:http://blog.csdn.net/weyuli/article/details/8727995


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。