UVa 12294 : RPG battles

問題リンク : http://uva.onlinejudge.org/external/122/12294.html

問題概要 :
ゲームの主人公の初期の力はpであり、これからn個のステージを全て入力で与えられた順番でクリアしなければならない ( できない場合は"Impossible"と出力 )
各ステージは p1, p2, t1, t2, w1, w2というパラメータで表される
現在の自分の力 p が p1 未満であるとき、そのステージはクリアできない
p がp1以上p2以下であるとき、そのステージをクリアするために t1 から t2 の間でlinearyに時間がかかる ( ここはコード見てほしい
p がp2以上のとき、 クリアにはt2秒かかる
ステージをクリアすることで2種類の薬がそれぞれw1個とw2個得られる
w1個得られる薬は、それを１つ飲むことで力を１上げることができる
w2個得られる薬は、それを１つ飲むことで力を二倍にできる
これらの薬は戦闘前に所有している範囲で任意の個数ずつ飲むことができる

全てのステージをクリアするためにかかる時間の最小を求めよ

解法 :
DPする
dp[ステージ番号][現在の力][現在所有している力を2倍にする薬の数] := 最小の時間
明らかに、力を１上げる薬は手に入れた時点で即飲んで良い
2倍になる薬はタイミングによって損得があるので、状態として持つ
ただし、2倍の薬を7回使用した時点で必ず力は100を超え、今後のステージを全て最短でクリアできるようになるので８個以上は必要ない

コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-4)
#define equals(a,b) (fabs((a)-(b))<EPS) 
 
using namespace std;
 
const double DINF = 1e20;
const string NO = "Impossible";
double dp[1010][110][8];
 
int n,power,pow2[10],w[2][1100];
double p[2][1100], t[2][1100];
 
int main(){
  pow2[0] = 1;
  REP(i,1,10) pow2[i] = pow2[i-1] * 2;
  while( cin >> n >> power, n|power ){
    rep(i,n) cin >> p[0][i] >> p[1][i] >> t[0][i] >> t[1][i] >> w[0][i] >> w[1][i];
    rep(i,n+1) rep(j,110) rep(k,8) dp[i][j][k] = DINF;
    dp[0][power][0] = 0;
    rep(phase,n){
      REP(cpower,1,101){
        rep(remain,8)if( !equals(dp[phase][cpower][remain],DINF) ){
          rep(use,remain+1){
            int npower = min(cpower * pow2[use],100);
            if( npower < p[0][phase] ) continue;
            double timer = t[0][phase] - ( t[0][phase] - t[1][phase] ) * ( ( min((double)npower,p[1][phase]) - p[0][phase] ) / ( p[1][phase] - p[0][phase] ) );
            dp[phase+1][min(npower+w[0][phase],100)][min(remain-use+w[1][phase],7)] = min(dp[phase+1][min(npower+w[0][phase],100)][min(remain-use+w[1][phase],7)],
                                                                               dp[phase][cpower][remain]+timer);
          }
        }
      }
    }
 
    double mini = DINF;
    rep(i,110) rep(j,8) mini = min(mini,dp[n][i][j]);
    if( equals(mini,DINF) ) puts("Impossible");
    else printf("%.2lf\n",mini);
  }
  return 0;
}