hdu3006状态dp

本文主要是介绍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());}}

这篇关于hdu3006状态dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---