[Coder's High 2014] Tons Of Damage

문제 링크

적당히 타격감있는 기댓값 DP 문제다.

 

divide by zero 예외를 놓치면 틀릴 수 있다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

using ld = long double;

ld C(int n, int r, ld x, ld y) {
    ld res = 1;
    rep(i,1,n) res *= i;
    rep(i,1,r) res /= i, res *= x;
    rep(i,1,n-r) res /= i, res *= y;
    return res;
}

const int N = 30;
int n;
ld p, q, r, s;
ld dp1[N], dp2[N];

int main() {
    int t; scanf("%d", &t); while (t--)
    {
        int n, a, b, c, d;
        scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);
        
        if (a == 0 and b == 0) { puts("0"); continue; }
        if (c == 0 and d == 0) { puts("0"); continue; }
        
        q = a/100.0L;
        p = b/100.0L;
        s = c/100.0L;
        r = d/100.0L;
        
        rep(i,1,n) {
            dp1[i] = p*(dp1[i-1]+1)+q*(dp1[i-1]*2);
            dp1[i] /= p+q;
            
            dp2[i] = r*(dp2[i-1]+1)+s*(dp2[i-1]*2);
            dp2[i] /= r+s;
        }
        
        ld ans = 0;
        rep(i,1,n) {
            rep(k,0,i) {
                ans += C(i,k,p+q,r+s)*dp1[k]*dp2[i-k];
            }
        }
        printf("%.7Lf\n", ans);
    }
}