問題
http://community.topcoder.com/stat?c=problem_statement&pm=13747&rd=16416
・N個のパンケーキが与えられ、i番目のパンケーキの幅はi+1になる。
また、各パンケーキのおいしさの値が与えられる。
・ここからパンケーキをひとつづつ選び、上に重ねていく。
ただし、現在積み重ねられている一番上のパンケーキより幅が大きいパンケーキを選んだらそこで終了となる。
・ランダムにパンケーキが重ねられるとき、パンケーキおおいしさの値の期待値を求める。
解き方
期待値の問題なのでｄｐが使えそう。（SRM607）
現在積み重ねられているパンケーキについて、
dp[現在の幅の広さ][現在のパンケーキの数]と定義する。
このとき、各dp[i][j]についてdp[0〜i][j+1]を更新してあげればよい。
コード
double dp[310][310];
class RandomPancakeStack {
public: double expectedDeliciousness(vector<int> d) {
memset(dp,0,sizeof(dp));
int n=d.size();
FORE(i,0,n+1)dp[n][0]=1.0;
//recurrence
for(int i=n-1;i>=0;i--){
for(int j=1;j<=n;j++){
for(int k=i+1;k<=n;k++)dp[i][j]+=dp[k][j-1]/(n-(j-1));
}
}
//transition
/*for(int i=n;i>=0;i--){
for(int j=0;j<n;j++){
for(int k=0;k<i;k++)dp[k][j+1]+=dp[i][j]/(n-j);
}
}*/
double ret=0.0;
FORE(i,0,n)FORE(j,0,n+1)ret+=d[i]*dp[i][j];
return ret;
}
};
class RandomPancakeStack {
public: double expectedDeliciousness(vector<int> d) {
memset(dp,0,sizeof(dp));
int n=d.size();
FORE(i,0,n+1)dp[n][0]=1.0;
//recurrence
for(int i=n-1;i>=0;i--){
for(int j=1;j<=n;j++){
for(int k=i+1;k<=n;k++)dp[i][j]+=dp[k][j-1]/(n-(j-1));
}
}
//transition
/*for(int i=n;i>=0;i--){
for(int j=0;j<n;j++){
for(int k=0;k<i;k++)dp[k][j+1]+=dp[i][j]/(n-j);
}
}*/
double ret=0.0;
FORE(i,0,n)FORE(j,0,n+1)ret+=d[i]*dp[i][j];
return ret;
}
};