Yukicoder023 技の選択

問題概要

体力がHの敵がいる。この敵を倒すまで、2種類の攻撃をする。
1: 通常攻撃　必ず$A$のダメージを与える。
2: 必殺技　　確率$\frac{2}{3}$で$D$のダメージを与える。
最終的に敵を倒すまでの回数の期待値を最小にするように攻撃を選んでいく。 敵を倒すまでの攻撃数の期待値は。

$1\leqq H,A,D\leqq10^4$

yukicoder023

解法

基本的な$DP$。$dp($$i):=i$のダメージを与えるために必要な最小の期待値　とする。 期待値は確率の逆数でできるので、簡単な漸化式になる。

計算量:$O(H)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    
    LL N;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int H, A, D;
        cin >> H >> A >> D;
        vector<double> dp(H + 1, INF);
        dp[0] = 0;
        FOR(i, 0, H) {
            dp[min(i + A, H)] = min(dp[min(i + A, H)], dp[i] + 1);
            dp[min(i + D, H)] = min(dp[min(i + D, H)], dp[i] + 1.5);
        }
        double ans = dp[H];
        cout << fixed << setprecision(3) << ans << "\n";
    
        return 0;
    }