久久综合五月丁香久久激情,久久精品www,久久精品国产亚洲AV蜜臀色欲

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 閱讀(194) 評論(0) 編輯收藏引用所屬分類: DP 、combination math

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

導航

統計

公告

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜