首页 > 专题系列 > Java解POJ > POJ 2436 Disease Management [解题报告] Java
2013
11-11

POJ 2436 Disease Management [解题报告] Java

Disease Management

问题描述 :

Alas! A set of D (1 <= D <= 15) diseases (numbered 1..D) is running through the farm. Farmer John would like to milk as many of his N (1 <= N <= 1,000) cows as possible. If the milked cows carry more than K (1 <= K <= D) different diseases among them, then the milk will be too contaminated and will have to be discarded in its entirety. Please help determine the largest number of cows FJ can milk without having to discard the milk.

输入:

* Line 1: Three space-separated integers: N, D, and K

* Lines 2..N+1: Line i+1 describes the diseases of cow i with a list of 1 or more space-separated integers. The first integer, d_i, is the count of cow i’s diseases; the next d_i integers enumerate the actual diseases. Of course, the list is empty if d_i is 0.

输出:

* Line 1: M, the maximum number of cows which can be milked.

样例输入:

6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1

样例输出:

5

温馨提示:

OUTPUT DETAILS:

If FJ milks cows 1, 2, 3, 5, and 6, then the milk will have only two diseases (#1 and #2), which is no greater than K (2).

解题代码:

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss=in.readLine().split(" ");
  int n=Integer.parseInt(ss[0]);
  int d=Integer.parseInt(ss[1]);
  int k=Integer.parseInt(ss[2]);
  int[] q=new int[n];
  for(int i=0;i< n;i++)
  {
   ss=in.readLine().split(" ");
   int a=Integer.parseInt(ss[0]);
   for(int j=0;j< a;j++){
	int f=Integer.parseInt(ss[j+1]);
	q[i]+=Math.pow(2, f-1);
   }	
  }
  System.out.println(f(d,k,q,0,0,0));
 }

 static int f(int d,int k,int[] q,int c,int s,int l)
 {	
  if(c==k)
  {
	int ans=0;
	s=~s;
	for(int i=0;i< q.length;i++)	
		if((s&q[i])==0)ans++;
	return ans;
   }
   if(l+k>d+c) return 0;
   int w=(int) Math.pow(2, l);
   return Math.max(f(d,k,q,c,s,l+1), f(d,k,q,c+1,s+w,l+1));
  }
}

  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3