読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 12294 : RPG battles

UVa 動的計画法

問題リンク : 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個得られる薬は、それを1つ飲むことで力を1上げることができる
w2個得られる薬は、それを1つ飲むことで力を二倍にできる
これらの薬は戦闘前に所有している範囲で任意の個数ずつ飲むことができる

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

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

コード:

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