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;
}