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

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>
            亚洲一区二区三区在线播放| 一区二区三区**美女毛片 | 久久看片网站| 久久视频这里只有精品| 米奇777在线欧美播放| 欧美成人蜜桃| 亚洲精品日韩精品| 亚洲一区免费| 久久午夜精品| 欧美日韩一区二区三区在线| 国产欧美日韩一区二区三区在线观看| 国产日韩欧美三区| 亚洲人www| 亚洲欧美一区二区在线观看| 久久一区二区视频| 亚洲免费播放| 欧美在线啊v一区| 欧美激情一二三区| 国产亚洲精品成人av久久ww| 最新日韩av| 欧美亚洲在线视频| 亚洲电影中文字幕| 宅男精品视频| 免费在线一区二区| 国产精品影音先锋| 亚洲精品看片| 久久精品91久久香蕉加勒比| 亚洲国产日韩在线| 欧美在线观看一二区| 欧美精品一卡| 伊人狠狠色丁香综合尤物| 亚洲午夜一级| 亚洲国产你懂的| 欧美一区二区精品| 欧美午夜不卡影院在线观看完整版免费| 免费成人小视频| 国产精品一卡| 亚洲少妇诱惑| 亚洲国产成人在线播放| 久久爱www| 国产精品日韩专区| 亚洲性人人天天夜夜摸| 亚洲国产精品欧美一二99| 欧美亚洲视频在线观看| 国产精品激情av在线播放| 亚洲人成免费| 免费在线国产精品| 久久成人在线| 国产一区二区精品在线观看| 亚洲欧美区自拍先锋| 亚洲精品国产精品国自产观看| 久久中文在线| 伊人蜜桃色噜噜激情综合| 久久精品国产亚洲高清剧情介绍| 亚洲视频1区2区| 欧美午夜不卡视频| 亚洲一区二区在线播放| 99爱精品视频| 欧美日韩国产小视频在线观看| 最新国产乱人伦偷精品免费网站| 欧美1区2区| 久久久亚洲人| 亚洲第一福利视频| 欧美~级网站不卡| 另类图片综合电影| 最新日韩中文字幕| 亚洲三级观看| 欧美视频在线观看免费网址| 中文日韩电影网站| 一区二区三区久久| 国产精品v日韩精品| 午夜久久久久久| 亚洲欧美国产一区二区三区| 国产精品视频| 久久久久久久精| 狼人天天伊人久久| 日韩一区二区精品| 一区二区三区欧美激情| 国产精品中文在线| 久久夜色精品国产噜噜av| 久久综合福利| 一区二区三区视频观看| 亚洲欧美日韩综合一区| 在线精品在线| 99视频一区二区| 国产喷白浆一区二区三区| 久久亚洲一区二区| 欧美激情精品久久久久| 亚洲一区二区三区在线看| 午夜精品久久久久久久| 最近中文字幕mv在线一区二区三区四区| 亚洲精品国产精品乱码不99按摩| 国产精品久久久久影院色老大 | 亚洲在线视频一区| 在线观看不卡av| 日韩一级片网址| 黑人操亚洲美女惩罚| 亚洲毛片在线免费观看| 国产一区二区三区免费不卡 | 亚洲剧情一区二区| 国产精品美女久久久| 六十路精品视频| 欧美天天综合网| 欧美/亚洲一区| 国产精品网站在线观看| 亚洲国产成人在线| 国产一区亚洲| 中文亚洲字幕| 亚洲精品男同| 久久九九热re6这里有精品| 一区二区三区视频观看| 另类综合日韩欧美亚洲| 性亚洲最疯狂xxxx高清| 欧美国产免费| 欧美**字幕| 国内成人精品视频| 亚洲永久在线观看| 一个色综合导航| 噜噜噜91成人网| 久久美女性网| 国产日产欧美精品| 亚洲丝袜av一区| 一区二区福利| 欧美连裤袜在线视频| 牛牛精品成人免费视频| 国产一区 二区 三区一级| 亚洲午夜av电影| 亚洲午夜一二三区视频| 欧美美女bbbb| 亚洲精品久久在线| 日韩视频二区| 欧美激情综合在线| 亚洲国产三级| 亚洲精品欧美一区二区三区| 巨乳诱惑日韩免费av| 美女福利精品视频| 伊人久久婷婷| 久久一日本道色综合久久| 久久在线视频| 欧美日韩国产a| 欧美高清免费| 在线电影国产精品| 久久av老司机精品网站导航| 久久精品二区亚洲w码| 国产日韩在线亚洲字幕中文| 性高湖久久久久久久久| 亚洲欧美日韩另类| 国产精品一区二区视频 | 亚洲欧美电影在线观看| 欧美片第一页| 亚洲日本黄色| 亚洲一区二区精品| 国产精品视频一二三| 欧美一级免费视频| 老司机aⅴ在线精品导航| 国产婷婷一区二区| 欧美一区二区三区另类| 亚洲一区二区三区视频播放| 国产精品国产福利国产秒拍| 亚洲一本视频| 欧美呦呦网站| 红桃视频亚洲| 欧美激情精品久久久久久黑人| 亚洲高清一区二| 国产精品99久久不卡二区| 欧美特黄一级| 亚洲欧美日韩成人| 久久精品一区二区| 亚洲欧洲另类| 国产精品一级久久久| 久久久噜噜噜久久中文字幕色伊伊| 久久精品官网| 在线观看精品| 欧美精品1区| 亚洲视频 欧洲视频| 久久久精品日韩欧美| 亚洲国产成人精品女人久久久 | 一本一道久久综合狠狠老精东影业| 国产精品区一区二区三| 久久久久欧美精品| 在线亚洲欧美视频| 男女激情久久| 久久国产精品第一页| 夜夜嗨av一区二区三区四季av | 国产精品自在欧美一区| 免费日韩成人| 欧美一区二区视频免费观看| 日韩午夜三级在线| 美女视频黄 久久| 亚洲欧美国产不卡| av不卡在线| 精品成人在线| 国产精品视频免费| 欧美日韩mp4| 久久久久久综合| 在线一区二区三区四区| 久久久午夜视频| 99视频精品| 亚洲福利国产| 国产精品激情av在线播放|