GCJ2012 Round 1A : Password Problem
問題概要
長さBのパスワードがあって、A文字目まで打ち込んでいる。これまでに打った文字が正しいかどうか確率が与えられるので、最適手順をとったときのパスワードが通るまでの手数の期待値の最小値を求める問題。
解法
期待値DP。状態数A、遷移3つなので素直に書いてやればよい。自分の解答は色々余計なことをしていてちょっと反省点が多い。まずはシンプルに書くべきなのに…。
import std.stdio, std.algorithm; import std.math; int A, B; real[] ps; void init(){ scanf("%d%d",&A, &B); ps = new real[](A); foreach(i; 0..A){ double p; scanf("%lf", &p); ps[i] = p; } } real solve(){ real ans = 0.0; real[] accum = new real[](A + 1); accum[0] = 0.0; foreach(i; 0..A){ accum[i+1] = accum[i] + log(ps[i]); } real[] dp = new real[](A + 1); dp[0] = B + 1; real mini = dp[0]; foreach(i; 1..A+1){ dp[i] = min(1.0 + mini, B - i + 1.0 + (1.0-exp(accum[i])) * (B + 1.0) , 1.0 + dp[0]); mini = min(1.0 + mini, dp[i]); } return dp[A]; } void main(){ int T; scanf("%d", &T); foreach(c; 0..T){ init; writefln("Case #%d: %.8f", c+1, solve); } }