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

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>
            国产乱肥老妇国产一区二| 欧美黄色一区| 中国成人黄色视屏| 欧美午夜久久久| 亚洲欧美综合精品久久成人| 亚洲女人小视频在线观看| 国产女主播视频一区二区| 久久久福利视频| 老司机免费视频一区二区| 亚洲欧洲在线播放| 一本色道久久88亚洲综合88| 国产精品永久免费视频| 久久婷婷国产麻豆91天堂| 噜噜噜在线观看免费视频日韩| 99re66热这里只有精品3直播| 亚洲手机视频| 一区二区三区在线高清| 欧美激情第二页| 国产精品久久久久久久久久妞妞| 久久久噜噜噜久久人人看| 免费在线看成人av| 亚洲一区二区三区精品动漫| 香蕉久久精品日日躁夜夜躁| 亚洲精品欧美一区二区三区| 亚洲神马久久| 伊人婷婷久久| 亚洲天堂第二页| 亚洲国产乱码最新视频| 中文日韩电影网站| 亚洲国产欧美一区二区三区久久 | 一区二区三区四区五区精品| 亚洲欧美综合一区| 日韩午夜免费视频| 久久av免费一区| 亚洲网站在线播放| 久久影音先锋| 久久免费国产精品| 国产精品乱码| 亚洲狼人精品一区二区三区| 激情亚洲网站| 亚洲在线日韩| 中国成人在线视频| 美女精品网站| 久久精品亚洲| 国产精品天天摸av网| 亚洲精品一品区二品区三品区| 樱桃成人精品视频在线播放| 亚洲一区二区三区免费观看 | 国产精品一区免费观看| 亚洲精品社区| 亚洲另类春色国产| 久久综合网络一区二区| 狂野欧美激情性xxxx| 国产伦理一区| 亚洲欧美日韩专区| 亚洲免费视频一区二区| 欧美精品精品一区| 亚洲国产精品精华液2区45| 国产综合久久久久久鬼色| 亚洲一区二区在线免费观看| 亚洲综合三区| 欧美午夜精品理论片a级大开眼界 欧美午夜精品理论片a级按摩 | 欧美亚韩一区| 亚洲卡通欧美制服中文| 一区二区激情| 欧美日韩高清在线播放| 亚洲精品美女91| 一区二区三区视频在线观看 | 小处雏高清一区二区三区| 羞羞视频在线观看欧美| 国产精品伦理| 欧美一区二区成人| 久久美女性网| 亚洲国产一区在线| 欧美极品在线播放| 一本色道久久综合亚洲精品不| 亚洲影视在线播放| 国产毛片精品国产一区二区三区| 午夜一级在线看亚洲| 久久久久久伊人| 91久久精品国产91性色| 欧美日韩a区| 先锋影音网一区二区| 久久艳片www.17c.com| 亚洲国产小视频| 国产精品国产三级国产aⅴ浪潮| 午夜精品亚洲一区二区三区嫩草| 久久深夜福利| 中文亚洲视频在线| 国产手机视频精品| 欧美成人性网| 亚洲综合色网站| 美女脱光内衣内裤视频久久网站| 日韩香蕉视频| 国内精品久久久久影院色| 欧美成人官网二区| 亚洲欧美日韩国产综合精品二区| 六月丁香综合| 亚洲天天影视| 亚洲国产精品激情在线观看| 欧美视频在线视频| 久久午夜电影| 亚洲欧美激情精品一区二区| 亚洲电影免费在线观看| 欧美一二区视频| 亚洲最新视频在线播放| 国产一区二区丝袜高跟鞋图片| 欧美成人性网| 久久久久久电影| 亚洲少妇最新在线视频| 亚洲国产裸拍裸体视频在线观看乱了中文 | 久久亚洲国产成人| 亚洲午夜精品久久久久久浪潮| 欧美成人一区二区三区片免费| 亚洲欧美日韩一区| 亚洲美女区一区| 影音先锋久久久| 国产视频在线观看一区| 欧美午夜精品久久久久久久| 欧美+亚洲+精品+三区| 久久成人羞羞网站| 亚洲一区二区不卡免费| 亚洲精品欧美精品| 欧美国产精品久久| 久久综合久久综合久久综合| 欧美一区二区三区日韩| 这里只有精品电影| 日韩亚洲一区在线播放| 亚洲国产欧美一区二区三区久久| 国内外成人在线| 国产视频精品xxxx| 国产日本欧美一区二区三区| 国产精品资源| 国产日韩欧美在线看| 国产精品v欧美精品v日韩精品| 欧美日韩另类国产亚洲欧美一级| 欧美极品欧美精品欧美视频| 农夫在线精品视频免费观看| 久久综合给合| 欧美va天堂在线| 欧美xart系列在线观看| 欧美高清不卡在线| 欧美黄色成人网| 欧美日韩国产成人高清视频| 欧美日韩精品久久| 欧美日韩一区综合| 国产精品二区在线| 国产欧美日韩综合一区在线观看| 国产精品一区毛片| 国产一区二区成人| 激情一区二区三区| 亚洲国产精品久久久久秋霞蜜臀 | 狠狠色狠狠色综合| 亚洲国产精品久久久久秋霞蜜臀 | 国产九九精品| 揄拍成人国产精品视频| 亚洲国产乱码最新视频| 99视频日韩| 欧美有码视频| 免费视频最近日韩| 亚洲精品日韩激情在线电影| 亚洲永久网站| 久久婷婷一区| 欧美视频在线免费看| 国产亚洲精品激情久久| 亚洲电影有码| 亚洲一区二区在线播放| 久久xxxx精品视频| 欧美大片在线影院| 99在线视频精品| 久久九九免费视频| 欧美伦理视频网站| 国产一区二区你懂的| 亚洲经典三级| 欧美一区二区三区男人的天堂| 免费美女久久99| 正在播放亚洲一区| 美女精品自拍一二三四| 国产精品播放| 亚洲国产视频直播| 欧美一区二区三区免费视频| 亚洲大胆视频| 午夜日韩视频| 欧美日韩在线播放三区| 在线观看91精品国产麻豆| 正在播放欧美视频| 久久综合九色| 亚洲综合精品自拍| 欧美区日韩区| 亚洲大胆女人| 久久激情视频久久| 日韩视频永久免费观看| 久久精品国产清高在天天线 | 久久综合伊人| 国产欧美日韩| 亚洲一区国产| 亚洲美女91| 欧美激情一区在线| …久久精品99久久香蕉国产 | 性久久久久久久|