No.23 技の選択 - yukicoder
- 確率・期待値・ゲーム戦略的な問題は苦手...。
- 試行回数の期待値についてはyukicoder No.23 : 技の選択 - ぱーぽーの競プロ記が参考になった。
- 最初 Exp[h] = 1/3*Exp[h] + Exp[h+A] + 2/3*Exp[h+D] + 1 を解いてモゴモゴしようとしていた。
- それに Exp[h] の h を現在の的の HP とかにして dp の方向を逆にしてちょっと面倒なことになっていた。(方針そのものが間違っていたんだけど。)
- 必殺技を k 回ためして当たらないとき、通常攻撃に切り替える。って戦略は最善になりえんのかな?と一瞬思った。
class ActionChoice {
public:
void solve(void) {
int H,A,D;
cin>>H>>A>>D;
vector<double> exp(H+1,0);
FOR(h, 1, H+1)
{
exp[h] = min(exp[max(h-A,0)] + 1, exp[max(h-D,0)] + 1.5);
}
cout<<exp[H]<<endl;
}
};