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
|
&&
||
?=
= += –= <<= >>=
,
从上到下依次降低~~~~~~~~~~~~~~~~~~··