ABC402E - Payment Required

#期待値 #DP

問題

https://atcoder.jp/contests/abc402/tasks/abc402_e

解法

期待値DPの典型。「ある状態から始めたときに、ありうるスコアの期待値の最大値」を持てば良い。そのうえで、後ろから逆算して最も期待値が大きくなるような行動を取ったとしたときの期待値が計算できる。
この問題だと、既にACした問題の集合 \(S\) 、残金 \(x\) を状態として \(\text{dp}_{s,x} :=\) ACした問題の集合 \(S\) 、残金が \(x\) 円のときの期待値の最大値とすればよい。遷移は、

\[\text{dp}_{S,x}=\max_{k=1}^N\begin{cases}P_k(S_k +\text{dp}_{S|k, x-C_j}) + (1-P_k)\text{dp}_{S|k, x-C_j} & \text{if } x\geq C_j\\0 & \text{otherwise}\end{cases}\]

と書くことができる。計算量は \(O(2^NNX)\) となる。 提出

void solve() {
    int n, x; cin >> n >> x;
    vector<long double> s(n), p(n);
    vector<int> c(n);
    rep(i,n) cin>>s[i]>>c[i]>>p[i];
    rep(i,n) p[i] = p[i]/100.0;
    vector<vector<long double>> dp(1<<n, vector<long double>(x+1, 0.0));
    rep(j,x+1) {
        per(i,(1<<n)) {
            long double exp = 0;
            rep(k,n) {
                int ni = i | (1<<k);
                if(i==ni) continue;
                if(j<c[k]) continue;
                long double val = p[k]*(s[k]+dp[ni][j-c[k]]) + (1.0-p[k])*dp[i][j-c[k]];
                chmax(exp, val);
            }
            dp[i][j] = exp;
        }
    }


    cout << fixed << setprecision(20) << dp[0][x] << '\n';
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t=1;
    //cin >> t;
    while(t--)solve();
}