亚洲日本电影,在线亚洲一区二区,国内外成人免费视频

江蘇大學

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

好吧，這道題思想開始就想到了，結(jié)果做的搓死了。。
題意是這樣，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])
然后結(jié)果應該是每隊至少做出一題的概率減去在這個基礎上所有隊做題數(shù)小于N的概率。
萬惡的StreamTokenizer，不知道讀入數(shù)據(jù)的時候出了什么詭異的問題，對照標程對拍，就是沒錯誤，一提交就WA！最后換Scanner，順利AC。。無語。
比賽的時候知道了，數(shù)據(jù)比較大或者浮點的情況下還是別用StreamTokenizer了。。

1

import java.io.*;
2

import java.text.DecimalFormat;
3

import java.util.Arrays;
4

import java.util.Scanner;
5

public class Main {
6

7

/**
8

* @param args
9

*/
10

11

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

41

total*=t1;
42

minus*=t2;
43

}
44

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

}
46

47

}
48

49

}
50

posted on 2010-11-02 01:23 yzhw 閱讀(215) 評論(0) 編輯收藏引用所屬分類: DP 、combination math

只有注冊用戶登錄后才能發(fā)表評論。


相關文章: pku3903 最長遞增字串的單調(diào)性優(yōu)化 pku 3998 Land Division DP斜率優(yōu)化 The 36th ACM/ICPC Asia Regional Dalian Online Contest 大連2011ICPC網(wǎng)絡賽個人題解 pku3124 The Bookcase 擴展背包好題 pku1202 Family DAG圖上的概率DP pku 1946 Cow Cycling 非常好的DP pku1948 Triangular Pastures DP+枚舉。海倫公式 pku1335 Digital Onion 遞歸 pku1332 Finding Liars DP 經(jīng)典好題 pku1337 A Lazy Worker 很詭異的DP

網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理