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

（解説ではない）