2013
11-10

# Check the difficulty of problems

Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms:

1. All of the teams solve at least one problem.

2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.

Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.

Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?

The input consists of several test cases. The first line of each test case contains three integers M (0 < M <= 30), T (1 < T <= 1000) and N (0 < N <= M). Each of the following T lines contains M floating-point numbers in the range of [0,1]. In these T lines, the j-th number in the i-th line is just Pij. A test case of M = T = N = 0 indicates the end of input, and should not be processed.

For each test case, please output the answer in a separate line. The result should be rounded to three digits after the decimal point.

2 2 2
0.9 0.9
1 0.9
0 0 0


0.972

//* @author:
import java.util.*;
public class Main
{

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
double dp[][]=new double[40][40];
int n,m,t;
double p,e,tp;
while (sc.hasNext()) {
m=sc.nextInt();
if(m==0) break;

t=sc.nextInt();
n=sc.nextInt();
e=tp=1;
for (int i=1;i<=t;i++) {
double tem=0;
dp[0][0]=1;
for (int j=1;j<=m;j++) {
p=sc.nextDouble();
if (j==1) {
dp[1][0]=1-p;
dp[1][1]=p;
}
else {
dp[j][0]=dp[j-1][0]*(1-p);
for (int k=1;k<=j;k++) dp[j][k]=dp[j-1][k-1]*p+dp[j-1][k]*(1-p);
}
}
for (int j=1;j< n;j++) tem+=dp[m][j];
tp*=tem;
for (int j=n;j<=m;j++) tem+=dp[m][j];
e*=tem;
}
System.out.printf("%.3f\n",e-tp);
}
}
}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

2. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。