• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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==0break;
            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 閱讀(200) 評論(0)  編輯 收藏 引用 所屬分類: DPcombination math

            <2011年2月>
            303112345
            6789101112
            13141516171819
            20212223242526
            272812345
            6789101112

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            jizzjizz国产精品久久| 欧美精品乱码99久久蜜桃| 日韩久久久久久中文人妻| 久久久久亚洲AV片无码下载蜜桃| 色婷婷综合久久久中文字幕| 国内精品久久久久影院一蜜桃| 久久精品视频网| 欧洲国产伦久久久久久久| 久久人人爽人人爽人人片av高请| 国产99久久久久久免费看| 色播久久人人爽人人爽人人片AV| 国内精品久久人妻互换| 色婷婷综合久久久久中文字幕| 精品熟女少妇AV免费久久 | 97久久精品无码一区二区| 91精品国产91久久久久久蜜臀| 亚洲伊人久久综合影院| 亚洲一区二区三区日本久久九| 国产精品亚洲综合久久| 久久综合狠狠色综合伊人| 狠狠综合久久AV一区二区三区| 久久精品国产一区二区三区| 久久综合88熟人妻| 日本加勒比久久精品| 国产精品久久一区二区三区| 精品久久久久久国产| 无码任你躁久久久久久| 狠狠色综合久久久久尤物| 国产精品久久久久久搜索| 久久久老熟女一区二区三区| 精品国产乱码久久久久久人妻| 香蕉久久AⅤ一区二区三区| 国产精品久久精品| 91精品国产高清久久久久久io | 国内高清久久久久久| 午夜精品久久久久久| 久久精品?ⅴ无码中文字幕| 国产—久久香蕉国产线看观看| 99精品国产在热久久| 久久国产精品成人免费| 国产精品对白刺激久久久|