TCO 2011 Round1 Div1 500

とぷこだ 過去問

問題

Fox Cielさんは1次元のマスの道路を左端から右端へ移動したい．
各マスには雨が降った場合泥だらけになる確率が与えられる．雨が降りました．
Cielさんは1マス先か2マス先に移動することができ，できるだけ泥だらけのマスを避けたい．
両端のマスは必ず乾いている時，泥だらけのマスを通る期待値を求めよ．

考え方

期待値dp．
最適な泥マスを通る回数の期待値を保持するdouble dp[]を用意する．もしマスの数n=3ならば2マス飛びで必ず泥マスを通らずに移動できるので，n>=4が問題．


あるマスiに注目する．このマスに来るにはi-1から来るかi-2から来るしかない．場合分け．
それぞれ泥マスの場合はx，乾いている場合はoとすると，

i-2のマス i-1のマス どういう動きをするか
x x i-1から来る場合かi-2から来る場合のどちらか期待値の少ない方(どっちも泥マスなのでdp[]+1)
o x i-2から来る
x o i-1から来る
o o i-1から来る(i-1まではdpが最適な値なはず)

という動きをするはずなので，

    REP(i,2,n){
      double xi1 = road[i-1]/100.0, oi1 = 1.0-xi1; //xi1:i-1が泥マスの確率 oi1:i-1が乾いている確率
      double xi2 = road[i-2]/100.0, oi2 = 1.0-xi2; //同上

      dp[i] = xi2 * xi1 * (min(dp[i-2], dp[i-1])+1); //泥マスを通らないといけない
      dp[i] += oi2 * xi1 * dp[i-2]; //泥マス回避
      dp[i] += xi2 * oi1 * dp[i-1]; //泥マス回避
      dp[i] += oi2 * oi1 * dp[i-1]; //泥マス回避
    
    }