hdu 3203 Door Repairing

한 문에 n명이 지나가다.사람마다 p의 확률로 문을 망가뜨릴 수 있다. 문을 수리하려면 a원이 필요하고 만약에 누군가가 지나갈 때 문이 고장나면 b원이 벌칙이다.기대한 최소 지출을 구하다.
비교적 뚜렷한 확률 dp문제는 관건은 유도 관계를 찾아내는 것이다.이 문제에서 만약 모든 사람이 통과한다면 문이 좋든 나쁘든 상관할 필요가 없을 것이다.이 조건이 있기 때문에 뒤에서 앞으로 유도하는 것이 비교적 쉽다.
dp[n][0]는 n번째 사람이 지나갈 때 문이 고장났다는 것을 나타낸다.dp[n][1]은 문이 좋다는 것을 나타낸다.
dp[n][0] = min(dp[n+1][0]+b, a+p*dp[n+1][0]+(1.0-p)*dp[n+1][1]);
dp[n][1] = p*dp[n+1][0]+(1.0-p)*dp[n+1][1];

#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <iostream>
#include <cmath>
using namespace std;
// http://acm.hdu.edu.cn/showproblem.php?pid=3203
#ifdef __GNUC__
typedef long long LL;
inline void opt64(LL a) {
    printf("%lld", a);
}
#else
typedef __int64 LL;
inline void opt64(LL a) {
    printf("%I64d", a);
}
#endif
const int MAXN = 100005;
//     
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n;
    double a, p, b;
    double f0, f1, p0, p1;
    while (scanf("%d%lf%lf%lf", &n, &p, &a, &b))
    {
        if (n==0 && a==0 && p==0 && b==0) break;
        p /= 100.0;
        f0 = min(a, b);
        f1 = 0.0;
        for (int i = 1; i< n; ++i)
        {
            p0 = min(f0+b, a+p*f0+(1.0-p)*f1);
            p1 = p*f0+(1.0-p)*f1;
            f0 = p0;
            f1 = p1;
        }
        printf("%.4lf
", f1);
    }
    return 0;
}