pku2151 Check the difficulty of problems 概率DP，可恶的StreamTokenizer!!!!!

好吧，这道题思想开始就想到了，结果做的搓死了。。
题意是这样，ACM比赛，T个队，M个题，第i个队做出第j个题的概率为p_i,j，求所有队至少做一题并且冠军队（可能有多个队）做出N题以上的概率
首先，每个队是独立的。
设dp[i][j]为前i个题目做出j题的概率，有dp方程dp[i][j]=dp[i-1][j-1]*(p[pos][i])+dp[i-1][j]*(1-p[pos][i])
边界条件：dp[0][0]=0;dp[i][0]=dp[i-1][0]*(1-p[pos][i])
然后结果应该是每队至少做出一题的概率减去在这个基础上所有队做题数小于N的概率。
万恶的StreamTokenizer，不知道读入数据的时候出了什么诡异的问题，对照标程对拍，就是没错误，一提交就WA！最后换Scanner，顺利AC。。无语。
比赛的时候知道了，数据比较大或者浮点的情况下还是别用StreamTokenizer了。。

import java.io.*;
2

import java.text.DecimalFormat;
3

import java.util.Arrays;
4

import java.util.Scanner;
5

public class Main {
6

/**
8

* @param args
9

*/
10

static double dp[][]=new double[35][35],map[][]=new double[1001][31];
12

static int m,t,n;
13

public static void main(String[] args) throws Exception{
14

Scanner in=new Scanner(System.in);
15

while(true)
16

{
17

m=in.nextInt();t=in.nextInt();n=in.nextInt();
18

if(m==0&&t==0&&n==0) break;
19

for(int i=1;i<=t;i++)
20

for(int j=1;j<=m;j++)
21

map[i][j]=in.nextDouble();
22

double total=1.0,minus=1.0;
23

for(int i=1;i<=t;i++)
24

{
25

for(int j=0;j<=m;j++)
26

Arrays.fill(dp[j],0.0);
27

double t1=0.0,t2=0.0;
28

dp[0][0]=1.0;
29

for(int j=1;j<=m;j++)
30

{
31

dp[j][0]=dp[j-1][0]*(1-map[i][j]);
32

for(int k=1;k<=m;k++)
33

dp[j][k]=dp[j-1][k-1]*map[i][j]+dp[j-1][k]*(1-map[i][j]);
34

}
35

for(int j=1;j<=m;j++)
36

{
37

t1+=dp[m][j];
38

t2+=(j<n?dp[m][j]:0);
39

}
40

total*=t1;
42

minus*=t2;
43

}
44

System.out.printf("%.3f\n",total-minus);
45

}
46

}
48

}
50

posted on 2010-11-02 01:23 yzhw 阅读(273) 评论(0) 编辑收藏引用所属分类: DP 、combination math

只有注册用户登录后才能发表评论。


相关文章: pku3903 最长递增字串的单调性优化 pku 3998 Land Division DP斜率优化 The 36th ACM/ICPC Asia Regional Dalian Online Contest 大连2011ICPC网络赛个人题解 pku3124 The Bookcase 扩展背包好题 pku1202 Family DAG图上的概率DP pku 1946 Cow Cycling 非常好的DP pku1948 Triangular Pastures DP+枚举。海伦公式 pku1335 Digital Onion 递归 pku1332 Finding Liars DP 经典好题 pku1337 A Lazy Worker 很诡异的DP

网站导航: 博客园博客园最新博文博问管理

2011年1月

日

一

二

三

四

五

六

统计

随笔 - 183
文章 - 2
评论 - 27
引用 - 0

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

搜索

积分与排名

积分 - 63886
排名 - 377