UVa 12324 : Philip J. Fry Problem

UVa演習 2014/6/10 (火) 問６

問題リンク : http://uva.onlinejudge.org/external/123/12324.html

問題概要：
スペースシップで旅をする
旅はn個のフェーズに分かれている
各フェーズはt[i]秒で終わる
各フェーズでb[i]個のスペースシップ加速素材を手に入れる
スペースシップ加速素材を手にいれた場合、その次のフェーズ以降で自由に使用することができる
ただしフェーズ中に使える加速素材は１個までである
加速装置を使用した場合フェーズの時間が半分になる
全てのフェーズを終えるのにかかる時間を最小にせよ

解法：
動的計画法
dp[フェーズ][今使える加速素材の数] := 最小の時間

コード:

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

const int IINF = INT_MAX;
int t[110],b[110],dp[110][110];

int main(){
  int n;
  while( cin >> n , n ){
    rep(i,n) cin >> t[i] >> b[i];
    rep(i,n+1) rep(j,n+1) dp[i][j] = IINF;

    dp[0][0] = 0;

    rep(i,n){
      rep(j,n+1){
        if( dp[i][j] == IINF ) continue;
        int cost = min(n,j + b[i]);
        dp[i+1][cost] = min(dp[i+1][cost],dp[i][j]+t[i]);
        if( j ) dp[i+1][cost-1] = min(dp[i+1][cost-1],dp[i][j]+t[i]/2);
      }
    }
    int mini = IINF;
    rep(i,n+1) if( dp[n][i] != IINF ) mini = min(mini,dp[n][i]);


    printf("%d\n",mini);
  }
  return 0;
}