hdu3006狀态dp

給你n個集合。集合中均為數字且數字的範圍在[1,m]内。m<=14。現在問用這些集合能組成多少個集合自己本身也算。

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NavigableSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;

import org.omg.CORBA.Object;




public class Main {


    public static void main(String[] args) throws IOException{

           StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in)); 
           InputReader in = new InputReader(System.in)  ;
           PrintWriter out = new PrintWriter(System.out) ;



           while(cin.nextToken() != cin.TT_EOF){
                int n = (int) cin.nval ;
                cin.nextToken() ; int m = (int) cin.nval ;
                new Task().solve(n , m , cin, out)  ;   //out.flush() ;
           }

           out.flush() ; 


    }


}

class   Task{

        boolean[] vis ;

        public void solve(int n , int m , StreamTokenizer  cin , PrintWriter out) throws IOException{
               int limit = 1<<m ;
               vis = new boolean[limit] ; 
               Arrays.fill(vis, false);
               for(int cas = 1 ; cas <= n ; cas++){
                    int val = 0 ;
                    cin.nextToken() ; int k = (int)cin.nval ;
                    for(int i = 0 ; i < k ; i++){
                         cin.nextToken() ; int j = (int)cin.nval ; 
                         val |= (1<< (j-1)) ;
                    }
                    vis[val] = true ;
                    for(int i = 0 ; i < limit ; i++){
                        if(vis[i]) vis[i|val] = true ;
                    }
               }
               int sum = 0 ; 
               for(int i = 1 ; i < limit ; i++) sum += vis[i] ? 1 : 0 ;
               out.println(sum) ; 
        }

}





class InputReader{
        public BufferedReader  reader;
        public StringTokenizer  tokenizer;

        public InputReader(InputStream stream){
                    reader = new BufferedReader(new InputStreamReader(stream), 32768) ;
                    tokenizer = null ;
        }

        public String next(){
                    while(tokenizer == null || ! tokenizer.hasMoreTokens()){
                        try{
                                tokenizer = new StringTokenizer(reader.readLine());
                        }catch (IOException e) {
                                throw new RuntimeException(e);
                        }
                    }
                    return tokenizer.nextToken();
        }

        public int nextInt() {
                    return Integer.parseInt(next());
        }

        public long nextLong() {
                    return Long.parseLong(next());
        }

}