青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

TC-srm249-Tableseat-DP-狀態排列

Posted on 2009-11-12 21:45 rikisand 閱讀(301) 評論(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

|

&&

||

?=

= += –= <<= >>=

,

 

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

 

 

 

 

 

 

 

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久久久久精| 欧美ed2k| 亚洲欧美日韩天堂一区二区| 国产精品成人一区| 亚洲尤物视频网| 亚洲男人的天堂在线| 国产自产2019最新不卡| 欧美国产第一页| 欧美精品大片| 欧美一区二区三区另类| 久久精品亚洲精品| 亚洲美女av黄| 午夜精品久久久久久久久| 在线日本成人| 一本色道**综合亚洲精品蜜桃冫| 国产精品久久国产精品99gif | 亚洲激情校园春色| 亚洲三级免费电影| 国产精品人人做人人爽人人添| 久热这里只精品99re8久| 欧美韩日视频| 久久精品av麻豆的观看方式| 农村妇女精品| 欧美一区二区三区免费视频| 免费观看久久久4p| 午夜激情综合网| 玖玖视频精品| 久久99伊人| 欧美激情无毛| 久久只有精品| 国产精品乱看| 亚洲黄页一区| 原创国产精品91| 亚洲特黄一级片| 亚洲精品在线视频| 久久精品国亚洲| 亚洲在线观看免费| 欧美黄色一区二区| 麻豆精品网站| 国产区在线观看成人精品| 亚洲精品国产精品国自产在线| 国内精品模特av私拍在线观看| 一本久久知道综合久久| 亚洲国产日韩欧美| 久久久久一区二区| 久久国内精品自在自线400部| 欧美日韩亚洲一区二区三区| 欧美成人一区二区三区在线观看| 国产精品女主播一区二区三区| 亚洲大胆人体视频| 极品日韩久久| 久久av二区| 久久久久久久97| 国产一区白浆| 欧美一区二区三区视频在线| 香蕉久久一区二区不卡无毒影院| 欧美视频成人| 一本久久a久久免费精品不卡| 99国产成+人+综合+亚洲欧美| 久久影院午夜论| 免费在线成人av| 伊人蜜桃色噜噜激情综合| 午夜精品久久久久| 久久国产精品亚洲va麻豆| 国产亚洲一区二区在线观看| 亚洲欧美成人一区二区三区| 亚洲欧美日韩中文视频| 国产精品毛片大码女人| 亚洲欧美中文另类| 久久久久久尹人网香蕉| 在线观看视频一区| 免费在线国产精品| 亚洲日本成人| 亚洲综合另类| 国产精品视频网| 欧美在线观看网站| 免费永久网站黄欧美| 亚洲美女中出| 国产精品久久久久久久久动漫| 亚洲性线免费观看视频成熟| 久久精品国产999大香线蕉| 国产主播一区二区三区四区| 久久久久高清| 亚洲国产日韩一级| 亚洲性夜色噜噜噜7777| 国产亚洲激情| 男女激情久久| 亚洲色诱最新| 欧美激情久久久久久| 99成人免费视频| 香蕉成人伊视频在线观看| 精品999久久久| 欧美精品免费播放| 香港久久久电影| 美女久久网站| 亚洲一区二区在线播放| 精品不卡在线| 欧美日韩在线免费观看| 欧美一区激情视频在线观看| 亚洲第一主播视频| 午夜精品区一区二区三| 亚洲第一区在线观看| 国产精品久在线观看| 玖玖综合伊人| 欧美一级夜夜爽| 亚洲人成网在线播放| 久久亚洲风情| 午夜精品久久久久久久| 亚洲国产裸拍裸体视频在线观看乱了中文| 欧美日韩国产a| 久久精品动漫| 亚洲一区免费视频| 亚洲精品久久久久久久久| 久久在线免费| 午夜久久美女| 99视频一区二区| 在线国产精品一区| 国产日韩在线一区| 欧美视频久久| 欧美成人一区在线| 欧美一区二区三区男人的天堂| 亚洲精品影视在线观看| 免费观看成人| 久久久久久综合网天天| 性色av香蕉一区二区| 99在线精品免费视频九九视| 亚洲高清视频在线观看| 韩国一区电影| 国产一区视频观看| 国产午夜一区二区三区| 国产精品日日摸夜夜添夜夜av| 欧美日韩亚洲一区二| 欧美激情亚洲国产| 欧美精品系列| 欧美激情亚洲| 久久精品国产69国产精品亚洲| 亚洲综合999| 亚洲免费一在线| 亚洲一区二区三| 亚洲嫩草精品久久| 午夜在线观看欧美| 欧美一区二区在线免费观看| 亚洲欧美一区二区三区在线| 亚洲一区二区三区在线看| 在线视频中文亚洲| 亚洲一区免费网站| 午夜性色一区二区三区免费视频| 亚洲线精品一区二区三区八戒| 亚洲午夜av| 午夜精品www| 久久精品综合| 开元免费观看欧美电视剧网站| 乱人伦精品视频在线观看| 久久夜色精品国产亚洲aⅴ| 蜜桃av久久久亚洲精品| 亚洲国产精品福利| 日韩一级精品| 亚洲欧美日韩区| 久久久久在线| 欧美精品日韩精品| 国产精品人人做人人爽| 国产一区二区看久久| **性色生活片久久毛片| 亚洲精品一区在线观看香蕉| 亚洲视频在线播放| 久久激情视频久久| 欧美国产在线观看| 亚洲天堂av在线免费观看| 欧美中文字幕不卡| 欧美不卡高清| 国产精品久久久久久久午夜| 国内精品嫩模av私拍在线观看| 亚洲国产裸拍裸体视频在线观看乱了中文 | 久久精品国产欧美亚洲人人爽| 久久色在线播放| 欧美日产在线观看| 国内精品久久久| 亚洲免费观看在线视频| 亚洲先锋成人| 可以看av的网站久久看| 亚洲经典一区| 香蕉av福利精品导航| 女人色偷偷aa久久天堂| 国产精品亚洲一区二区三区在线| 国内偷自视频区视频综合| 91久久夜色精品国产九色| 欧美一区二区视频在线| 亚洲经典视频在线观看| 久久精品国产第一区二区三区| 欧美日韩午夜| 亚洲国内自拍| 久久精品免费电影| 99人久久精品视频最新地址| 久久精品视频免费播放| 欧美看片网站| 伊大人香蕉综合8在线视| 午夜精品区一区二区三| 亚洲日本一区二区三区| 欧美在线三区| 国产九区一区在线|