問題
http://community.topcoder.com/stat?c=problem_statement&pm=13778&rd=16500
解き方
dpで解く。
dp[現在の位置][現在が1か0か][1が最初から連続しているかのフラグ]とする。
現在のビット０になったとき、
１が最初から連続していれば１回の操作が必要で、
連続していなければ２回の操作が必要になる。
#英出張中で出れなかったが、日本だと出場しやすい時間だったので出たかった…
コード
class Bitwisdom {
public: double expectedActions(vector<int> p) {
int n=p.size();
double dp[301][2][2];
memset(dp,0,sizeof(dp));
double ret=0;
dp[0][0][0]=(100-p[0])*0.01;
dp[0][1][1]=p[0]*0.01;
for(int i=1;i<n;i++){
ret+=dp[i-1][1][0]*(100-p[i])*0.02;
ret+=dp[i-1][1][1]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][0][0]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][1][0]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][1][1]*(100-p[i])*0.01;
dp[i][1][0]+=dp[i-1][0][0]*p[i]*0.01;
dp[i][1][0]+=dp[i-1][1][0]*p[i]*0.01;
dp[i][1][1]+=dp[i-1][1][1]*p[i]*0.01;
}
ret+=dp[n-1][1][1]+dp[n-1][1][0];
return ret;
}
};
public: double expectedActions(vector<int> p) {
int n=p.size();
double dp[301][2][2];
memset(dp,0,sizeof(dp));
double ret=0;
dp[0][0][0]=(100-p[0])*0.01;
dp[0][1][1]=p[0]*0.01;
for(int i=1;i<n;i++){
ret+=dp[i-1][1][0]*(100-p[i])*0.02;
ret+=dp[i-1][1][1]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][0][0]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][1][0]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][1][1]*(100-p[i])*0.01;
dp[i][1][0]+=dp[i-1][0][0]*p[i]*0.01;
dp[i][1][0]+=dp[i-1][1][0]*p[i]*0.01;
dp[i][1][1]+=dp[i-1][1][1]*p[i]*0.01;
}
ret+=dp[n-1][1][1]+dp[n-1][1][0];
return ret;
}
};