#DP #Expectation #RecursiveExpectation #Solved #TopCoder

BankLottery.cpp

//https://arena.topcoder.com/#/u/practiceCode/14353/12782/10988/1/305321
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int n, jackpot, total;
vector<int> accounts;

double cache[1005][1005];
double calcExpect(int i, int wins) {
    if(i == n)
        return wins*jackpot+accounts[0];
    double &ret = cache[i][wins];
    if(ret + 1 > 1e-9)
        return ret;
    ret = 0.0;
    double p = (accounts[0]+wins*jackpot)/(total*1.0 + i*jackpot);
    ret += p * calcExpect(i+1, wins+1);
    ret += (1-p) * calcExpect(i+1, wins);
    return ret;
}
/*
int main() {
    total = 0;
    int x, tmp;
    cin>>x;
    lp(i, x) {
        cin>>tmp;
        accounts.push_back(tmp);
        total+=tmp;
    }
    cin>>jackpot>>n;
    clr(cache, -1);
    cout <<setprecision(16)<< calcExpect(0, 0) << endl;
    return 0;
}
*/
class BankLottery {
public:
    double expectedAmount(vector<int> accounts1, int jackpot1, int n1) {        
        total = 0;
        int x = accounts1.size();
        accounts = accounts1;
        lp(i, x) {
            total+=accounts[i];
        }
        jackpot = jackpot1;
        n = n1;
        clr(cache, -1);
        return calcExpect(0, 0);
    }
};