yukicoder 0023 技の選択

概要

初期値 $H$ の敵の HP を $0$ 以下にしたい. 毎ターン, 次の二つの行動のどちらか一方を出来る.

• 確率 $1$ で HP を $A$ 減らす.
• 確率 $2/3$ で HP を $D$ 減らし, $1/3$ でなにも起きない.

毎ターンの分布は独立.

かかるターン数の期待値を最小化する戦略をとった時, そのターン数を答えよ.

制約

$1 \le H, A, D \le 10^4$

解法

dp[残りHP h] = HP が h の状態から, ちょうど 0 にするのに, 最適な戦略でかかるターン数の期待値

を更新する. さすがにこれくらいだとメモ化再帰より楽そう.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long double R;

bool solve(){
    int h, a, d; cin >> h >> a >> d;
    vector<R> res(h + a + d + 100, numeric_limits<R>::infinity());
    res[0] = 0;
    rep(i, h){
        chmin(res[i + a], res[i] + 1);
        chmin(res[i + d], res[i] + 1.5);
    }
    cout << *min_element(begin(res)+h, end(res)) << endl;
    return true;
}