土下座しながら探索中

主に競技プログラミング

Codeforces 487A : Fight the Monster

問題リンク : Problem - A - Codeforces

問題概要 :
君はモンスターと戦っている
君の攻撃力はATKy,守備力はDEFy,体力はHPy
モンスターの攻撃力はATKm,守備力はDEFm,体力はHPm
1ターンに君の体力はmax(0,ATKm-DEFy)減り、モンスターの体力はmax(0,ATKy-DEFm)減る
戦闘が始まる前に魔法を使って体力、守備力、攻撃力を上げることができる
ただし、それぞれを1上げるためにはそれぞれh,d,aのコストがかかる
自分の体力が0より大きく、モンスターの体力が0以下になれば勝利である
君が勝利するために必要なコストの最小値をもとめよ

制約 :
入力はすべて1以上100以下

解法:
入力は全て1以上100以下なので
攻撃力は多くても200までしか上げなくてよい
200上げると君の攻撃力は少なくとも201になるのでモンスターの守備力が最大でも100なので1ターンで倒せる
守備力についても100上げれば君の守備力は101になりモンスターから一切ダメージを受けなくなる
体力については、攻撃力と守備力さえ決まれば後何ターン必要か分かる
つまり、攻撃力と守備力を全て試せば良い

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main(){
  int HPy,ATKy,DEFy,HPm,ATKm,DEFm,h,a,d;
  cin >> HPy >> ATKy >> DEFy;
  cin >> HPm >> ATKm >> DEFm;
  cin >> h >> a >> d;
  int mini = INT_MAX;
  rep(da,201){
    rep(dd,101){
      int atk = ATKy + da;
      int def = DEFy + dd;
      if( atk <= DEFm ) continue;
      int time1 = ceil( (double)HPm / (double)( atk - DEFm ) );
      int HP = HPy - ( ATKm - def ) * time1;
      if( HP > 0 ) {
	mini = min(mini,da*a+dd*d);
      } else {
	int need_time = ( ATKm - def ) * time1 - HPy + 1;
	mini = min(mini,da*a+dd*d+need_time*h);
      }
    }
  }
  cout << mini << endl;
  return 0;
}