首页 > 专题系列 > Java解POJ > POJ 2151 Check the difficulty of problems [解题报告] Java
2013
11-10

POJ 2151 Check the difficulty of problems [解题报告] Java

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])
    这里写错了吧。