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

好吧，这道题思想开始就想到了，结果做的搓死了。。
题意是这样，ACM比赛，T个队，M个题，第i个队做出第j个题的概率为pi,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了。。
 1import java.io.*;
 2import java.text.DecimalFormat;
 3import java.util.Arrays;
 4import java.util.Scanner;
 5public 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 阅读(187) 评论(0)  编辑 收藏 引用 所属分类: DP 、combination math


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜