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

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>
            美国三级日本三级久久99| 亚洲一区二区三区激情| 黄色一区二区在线观看| 伊人成人在线视频| 亚洲高清自拍| 亚洲美女精品久久| 亚洲一二三区精品| 久久国产精品一区二区三区| 久热精品在线视频| 亚洲欧洲日本在线| 中文在线资源观看网站视频免费不卡 | 亚洲人成啪啪网站| 亚洲天堂免费在线观看视频| 欧美在线影院在线视频| 欧美电影专区| 国产精品一页| 亚洲激情电影在线| 香蕉av福利精品导航| 欧美激情1区2区3区| 亚洲一二三区在线| 免费不卡亚洲欧美| 国产无遮挡一区二区三区毛片日本| 国内综合精品午夜久久资源| 99国产精品久久久| 久久精品国产视频| 亚洲狼人精品一区二区三区| 久久久精品国产一区二区三区| 欧美理论电影在线观看| 国产一区二区三区久久精品| 一区二区三区日韩精品| 久久久久高清| 亚洲视频日本| 欧美高清视频免费观看| 午夜国产不卡在线观看视频| 蜜桃久久精品乱码一区二区| 国产日韩精品一区二区三区| 日韩视频精品| 女人色偷偷aa久久天堂| 午夜久久久久久| 欧美性开放视频| 日韩天天综合| 欧美激情网站在线观看| 久久精品1区| 美女诱惑黄网站一区| 国产精品日韩欧美| 亚洲视频网站在线观看| 亚洲高清在线播放| 久久婷婷国产综合国色天香| 国产一区 二区 三区一级| 亚洲一区在线直播| 99精品视频免费全部在线| 欧美成人午夜影院| 亚洲人成人一区二区在线观看| 久久婷婷色综合| 亚洲伦理中文字幕| 欧美成人精品1314www| 欧美在线日韩| 精品动漫3d一区二区三区| 久久久久成人网| 久久国产直播| 亚洲电影免费观看高清完整版在线观看 | 国产精品亚洲人在线观看| 亚洲伊人伊色伊影伊综合网| 亚洲精品你懂的| 欧美久久99| 亚洲摸下面视频| 亚洲一区二区三区在线| 国产精品亚洲人在线观看| 欧美中文字幕在线播放| 久久国产精品久久久久久| 樱花yy私人影院亚洲| 欧美激情中文字幕一区二区 | 亚洲人成在线观看| 欧美日本一道本| 亚洲永久精品大片| 欧美在线啊v| 亚洲国产三级网| 99视频一区二区| 国产一级揄自揄精品视频| 欧美α欧美αv大片| 欧美激情免费观看| 亚洲欧美日韩国产另类专区| 午夜视频一区| 亚洲欧洲视频| 亚洲视频久久| 国产中文一区二区三区| 欧美国产日韩一区二区在线观看| 欧美精品三级日韩久久| 亚洲欧美伊人| 卡一卡二国产精品| 亚洲已满18点击进入久久| 久久国产精品99国产| 亚洲日韩第九十九页| 9色精品在线| 国产乱子伦一区二区三区国色天香 | 国产欧美日韩一级| 久久久久欧美| 欧美日本视频在线| 久久综合伊人77777蜜臀| 欧美日韩国产综合新一区| 欧美综合激情网| 欧美日韩国产精品一区| 国产精品欧美一区喷水| 欧美国产先锋| 国产日韩一区二区三区在线| 亚洲人成人77777线观看| 激情一区二区三区| 亚洲视频电影图片偷拍一区| 91久久线看在观草草青青| 欧美亚洲系列| 亚洲欧美电影在线观看| 欧美福利视频| 免费日韩成人| 国语自产精品视频在线看一大j8| 一区二区三区.www| 99国产一区| 久久亚洲综合色一区二区三区| 亚洲欧美福利一区二区| 欧美日韩久久| 亚洲国产另类久久久精品极度| 韩国精品久久久999| 亚洲欧美福利一区二区| 亚洲小说区图片区| 久久av资源网| 国产精品入口日韩视频大尺度| 亚洲精品国产精品国自产观看 | 老司机精品导航| 影视先锋久久| 欧美亚洲视频在线看网址| 亚洲在线播放电影| 欧美日韩欧美一区二区| 欧美大胆成人| 136国产福利精品导航网址| 欧美一区二区免费观在线| 夜夜精品视频| 欧美人在线视频| 亚洲欧洲日本国产| 亚洲国产精品视频一区| 久久国产加勒比精品无码| 欧美在线三级| 国产专区精品视频| 久久免费国产精品| 欧美jizz19性欧美| 91久久线看在观草草青青| 欧美电影美腿模特1979在线看| 亚洲电影欧美电影有声小说| 亚洲美女啪啪| 欧美色综合网| 午夜精彩国产免费不卡不顿大片| 亚洲欧美综合| 国产伦精品一区二区三区| 午夜久久久久| 欧美顶级大胆免费视频| 亚洲剧情一区二区| 国产精品久久9| 欧美一区二区三区在线免费观看| 老巨人导航500精品| 亚洲破处大片| 国产精品高潮呻吟久久| 欧美一级欧美一级在线播放| 欧美a级一区二区| 亚洲婷婷在线| 国产曰批免费观看久久久| 蜜臀久久99精品久久久画质超高清| 亚洲片国产一区一级在线观看| 亚洲在线中文字幕| 国内精品久久久久影院薰衣草| 久久综合九色九九| 一区二区三区毛片| 麻豆91精品| 中日韩视频在线观看| 黄色成人在线网址| 欧美日韩在线高清| 久久精选视频| 中日韩美女免费视频网址在线观看 | 国产日韩亚洲欧美精品| 欧美高清视频在线播放| 亚洲欧美日韩国产另类专区| 亚洲国产精品电影在线观看| 午夜宅男久久久| 亚洲精选视频免费看| 国产日韩在线一区| 欧美日韩一区二区在线观看视频 | 久久久福利视频| 正在播放欧美一区| 激情久久影院| 国产精品美女久久久久久久 | 一本一道久久综合狠狠老精东影业| 久久大逼视频| 亚洲一区二区免费| 91久久极品少妇xxxxⅹ软件| 国产视频亚洲精品| 欧美体内谢she精2性欧美| 老司机aⅴ在线精品导航| 亚洲欧美视频在线| 一区二区三区成人精品| 亚洲人成人一区二区在线观看| 欧美成人小视频| 麻豆9191精品国产| 久热这里只精品99re8久|