• <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-狀態排列

            Posted on 2009-11-12 21:45 rikisand 閱讀(291) 評論(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 數字表達教程里的習題~ 題目大意 求使用桌子的期望。由于到來group的個數不定,每個group需要的桌子不定,使確定期望變得困難。但考慮對于numTables來說,使用桌子的狀態僅僅有 2^numTables種,因此考慮在這些狀態改變的過程中來計算期望,也就是計算在每個狀態下面的期望桌子數目。在每個狀態到達時,依次考慮來了一個group需要k個位子,如果r種安排可以滿足k個位子,那么當前狀態的期望值要加上 來k個位子的概率 X (r種安排分別的期望和 / r) 其中求r中安排期望和則需要 遞歸調用函數。顯然利用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
                    }

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

            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++)  //循環最多numTables+1 次

            {flag=true;

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

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

                 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;

             

            優先級很容易錯:

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

            典型的幾個

            ++ -- <post-incre-decre>

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

            *  / %

            + -

            >>  <<

            < <= > >=

            == !=

            &

            ^ xor

            |

            &&

            ||

            ?=

            = += –= <<= >>=

            ,

             

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

             

             

             

             

             

             

             

            久久精品成人免费看| 久久亚洲精品成人AV| 久久综合久久性久99毛片| 久久久久99精品成人片三人毛片| 国内精品久久久久久不卡影院 | 久久久久亚洲Av无码专| 成人综合伊人五月婷久久| 国产叼嘿久久精品久久| 2021国产精品久久精品| 久久国产一区二区| 中文字幕无码av激情不卡久久| 久久综合亚洲欧美成人| 国产精品欧美久久久久天天影视| 亚洲人成无码久久电影网站| 久久发布国产伦子伦精品 | 91精品国产乱码久久久久久| 久久九九久精品国产免费直播| 亚洲狠狠婷婷综合久久蜜芽| 久久99精品久久久久久齐齐| 久久久久女人精品毛片| 香蕉久久夜色精品国产2020| 51久久夜色精品国产| 国内高清久久久久久| 91精品国产高清久久久久久国产嫩草 | 色综合合久久天天综合绕视看| 国产精品亚洲综合久久| 国产福利电影一区二区三区久久老子无码午夜伦不 | 香蕉久久久久久狠狠色| 伊人丁香狠狠色综合久久| 麻豆成人久久精品二区三区免费 | 日韩精品久久无码中文字幕| 美女久久久久久| 久久精品国产一区二区三区不卡| 99麻豆久久久国产精品免费| 久久久久久伊人高潮影院| 日本久久中文字幕| 久久久久无码专区亚洲av| 国产高潮久久免费观看| 久久国产精品99久久久久久老狼| 久久人妻少妇嫩草AV无码专区| 亚洲中文久久精品无码|