• <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>

            TC-srm249-Tableseat-DP-狀態(tài)排列

            Posted on 2009-11-12 21:45 rikisand 閱讀(290) 評論(0)  編輯 收藏 引用 所屬分類: TopcoderAlgorithm

            Your restaurant has numTables tables to seat customers. The tables are all arranged in a line. If a large party of customers comes in, a group of adjacent tables will be used. Which group of tables is entirely up to the customer. Since you cannot predict this, assume all possible choices occur with equal probability. What you can predict is the size of each group of customers that arrives. Element i of probs gives the probability, in percent, that an entering party will need i+1 tables. Assuming nobody leaves, return the expected number of tables you will use before a party must be turned away. This only occurs if there is no place to seat them.

            Method signature:
            double getExpected(int numTables, vector <int> probs)

            numTables will be between 1 and 12 inclusive.
            probs will contain between 1 and 12 elements inclusive.
            Each element of probs will be between 0 and 100 inclusive.
            The elements of probs will sum to 100.

             

            misof 數(shù)字表達教程里的習題~ 題目大意 求使用桌子的期望。由于到來group的個數(shù)不定,每個group需要的桌子不定,使確定期望變得困難。但考慮對于numTables來說,使用桌子的狀態(tài)僅僅有 2^numTables種,因此考慮在這些狀態(tài)改變的過程中來計算期望,也就是計算在每個狀態(tài)下面的期望桌子數(shù)目。在每個狀態(tài)到達時,依次考慮來了一個group需要k個位子,如果r種安排可以滿足k個位子,那么當前狀態(tài)的期望值要加上 來k個位子的概率 X (r種安排分別的期望和 / r) 其中求r中安排期望和則需要 遞歸調用函數(shù)。顯然利用memo可以減少重復計算于是有下面的解法:

            vector<double> p;
            double dp[1<<13];   
            int tb;
            double solve(int cur){
                if(dp[cur]>-1.0)return dp[cur];    //memo available
                double ret=0;double sum;int kind;
                for(int i=0;i<p.size();i++){
                    sum=0,kind=0;
                    int mask=(1<<(i+1))-1;    //new group need i+1 adjacent tables
                    for(int j=0;j+i+1<=tb;j++){
                        if((cur&(mask<<j))==0){    //current pattern could meet the need
                            sum+=solve(cur+(mask<<j))+i+1;    //total method ++
                            kind++;
                        }
                    }
                    if(kind!=0)sum/=kind; //caculate the average need
                    ret+=sum*p[i];
                }
                dp[cur]=ret;
                return ret;
            }

                    double getExpected(int numTables, vector <int> probs)
                    {
                            tb=numTables;
                            REP(i,1<<13)dp[i]=-1.0;
                            p.resize(probs.size());
                            for(int i=0;i<probs.size();i++)p[i]=probs[i]*0.01;
                            return solve(0);//the beginning pattern
                    }

            看比賽中有另一種解法,即根據(jù)題目,在到達每次fail to serve a group 的時候 根據(jù)此時的桌子數(shù)量,和到達這種狀態(tài)的概率 來計算:

            dp[1<<13][15];memset(dp,0,sizeof(dp));// :D lucily I can do this for 0

            double fails=0.0;bool flag ;

            for(int i=1;i<=numTables+1;i++)  //循環(huán)最多numTables+1 次

            {flag=true;

            for(int j=0;j<p.size();j++){

                 int mask=(1<<(j+1))-1;//注意移位運算符的優(yōu)先級低,注意加括號

                 for(int k=0;k<=(1<<numTables-1);k++){

                      if(dp[k][i-1]<=0.0)continue;

                      flag=false;

                      int cnt=0;

                      for(int m=0;m+j+1<=numTables;m++) if((mask<<m)&k==0)cnt++;

                      if(cnt)for(int m=0;m+j+1<=numTables;m++)if((mask<<m)&k==0)dp[mask<<m|k][i]+=dp[k][i-1]*p[j]/cnt;

                      if(!cnt){

                             int b=k,bn=0;while(b){if(b&1)bn++;b>>=1;}

                             fail+=dp[k][i-1]*bn; 

                     }

                }

            }

            if(flag)return fail;//all dp[][k]==0.0

            }

            return fail;

             

            優(yōu)先級很容易錯:

            http://www.cppreference.com/wiki/operator_precedence~。~

            典型的幾個

            ++ -- <post-incre-decre>

            ~ <bitwise complement> !<not>&<addresss> *<dereference>&<address>

            *  / %

            + -

            >>  <<

            < <= > >=

            == !=

            &

            ^ xor

            |

            &&

            ||

            ?=

            = += –= <<= >>=

            ,

             

            從上到下依次降低~~~~~~~~~~~~~~~~~~··

             

             

             

             

             

             

             

            色综合久久综合中文综合网| 精品久久久无码中文字幕| 日韩美女18网站久久精品| 久久久久久久波多野结衣高潮 | 久久综合久久综合亚洲| 一本一道久久综合狠狠老| 国产精品99久久99久久久| 欧美国产精品久久高清| 久久天天躁狠狠躁夜夜avapp | 久久久久国产精品嫩草影院| 99精品国产综合久久久久五月天| 国产精品美女久久久久久2018| 久久无码一区二区三区少妇 | 蜜桃麻豆www久久| 偷窥少妇久久久久久久久| 国产精品久久久亚洲| 久久亚洲精品无码VA大香大香| 久久精品国产亚洲av高清漫画| 久久AAAA片一区二区| 2021精品国产综合久久| 久久久精品人妻一区二区三区蜜桃| 久久婷婷五月综合色奶水99啪| 欧美日韩精品久久久久| 国产精品美女久久久久久2018 | 日本三级久久网| 久久精品国产亚洲av影院| 久久精品国产乱子伦| 久久精品国产一区二区| 久久精品国产99国产精品澳门| 午夜久久久久久禁播电影| 青青青青久久精品国产h久久精品五福影院1421 | 国内精品人妻无码久久久影院导航| 国产精品热久久毛片| 高清免费久久午夜精品| 99久久久国产精品免费无卡顿| 日韩AV无码久久一区二区| 久久久噜噜噜久久熟女AA片 | 亚洲国产天堂久久综合网站| 99久久这里只有精品| avtt天堂网久久精品| 91精品国产乱码久久久久久|