yukicoder No.23 技の選択
問題
体力Hの敵を必ず当たる通常攻撃と2/3の確率で当たる必殺技で倒したい。攻撃力は、通常攻撃はA、必殺技はDであたえられる。敵を倒すまでにかかる攻撃回数の期待値を求めよ。
感想
有効な手が出るまでの回数の期待値は、その有効な手が出る確率の逆数ってことを最近知ったので解けた!
・必殺技が出る(有効な手が出る)確率=2/3
・それが出るまでの回数の期待値=(2/3)^-1
DPは苦手なのでメモ化再帰で
#include <iostream> #include <cmath> #include <vector> #include <utility> #include <queue> #include <map> #include <string> #include <cstring> #include <list> #include <algorithm> #define INF 114514 using namespace std; typedef pair<double,double> P; typedef long long ll; int a,d; double memo[100001]; double dfs(int h){ if(h <= 0)return 0; if(memo[h] != -1)return memo[h]; return memo[h] = min(dfs(h-a) + 1 ,dfs(h-d) + 1.5); } int main(void) { int h; for(int i=0;i<100001;i++)memo[i] = -1; cin >> h >> a >> d; printf("%.10f\n",dfs(h)); }
(解説ではない)