yukicoder 0023 技の選択

問題文

概要

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

毎ターンの分布は独立.

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

制約

$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;
}
download full source code

Tags

yukicoder
期待値
DP

Comments

comments powered by Disqus