2013
11-11

# 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
{
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++)
{
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