4996 - Scientefic Experiment

4996 - Scientefic Experiment
Asia - Kuala Lumpur - 2010/2011
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4996

問題概要

ビルから卵を落とす。
何回か卵を実際に落として、卵を落としても割れないもっとも高い階を求めよ。
0階では卵が必ずわれない。
n階では必ず割れることが保証されている。
ビルの中でx円で卵が売っている。
卵を持たずにビルに入場するにはy円かかる。
卵を持ってビルに入場するにはz円かかる。
落としてみて割れなかった卵は必ず次の実験に使わなければならない。
実験の最後に割れなかった卵があった場合は、卵をx/2円で売ることができる。
xは必ず偶数である。
かかるお金を最小にしようと行動した場合、
最悪ケースで何円かかるでしょう。

解法

dp
答えになり得る候補の範囲の広さを状態にする。
答えになり得る場所全てに卵を落とす。
その卵が割れた場合と割れなかった場合の最悪のケースの方を
それぞれの場所に卵を落とす場合を求め、
その結果の最小を取る。
そうすると、最悪なケースを最小にした場合のコストがもとまる。

ソース

#include<iostream>
#include<algorithm>
#include<cstdio>

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

using namespace std;
typedef long long lli;
const int INF = 1000000000;

const int N = 1002;

bool used[N][2];
lli dp[N][2];
int x, y, z, n;
void init(){
  rep(i, n+2){
    rep(k, 2){
      used[i][k] = false;
    }
  }
}
lli solve(int range, bool egg){
  if(used[range][egg])return dp[range][egg];
  if(range == 1){
    if(egg)return -x/2;
    return 0;
  }
  lli base, ret = INF;
  if(egg)base = z;
  else base = x + y;
  REP(i, 1, range){
    ret = min(ret, max(solve(i, false), solve(range-i, true)));
  }
  used[range][egg] = true;
  dp[range][egg] = ret + base;
  return ret + base;
}


int main(){
  int T;
  cin >> T;
  rep(tc, T){
    cin >> n >> x >> y >> z;
    init();
    printf("Case %d: %Ld\n", tc+1, solve(n, false));
  }
  return 0;
}