積み木 / Blocks [JOI2018 予選模試 D]

https://www.hackerrank.com/contests/joi2018/challenges/blocks-3

前提知識

• 動的計画法

解説

地点2～Nにある積み木は地点1に置くか、置かないかで考えるだけで良い。
他の地点に一旦移動させて、一気に地点1に移動するような行為をしてもコストは変わらないためである。
状態が2^Nになったので、DPかなと言う感じになる。
dp[i][hi] := 地点iまでの積み木を使って、地点1の高さをhiにするための消費体力の最小値
hiは普通にやると10^6くらい必要になるが、目標の高さH以上は特に考える必要が無いため、hi≦10^3で良い。
状態数がO(NH)で遷移が取る取らないの2択なので間に合う。
正確な遷移は下のプログラムを見てもらうといいが、min(H, hi+h[i])でhiに上限を加えることで状態数を削減している。

int N, H, w[1010], h[1010];
ll dp[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> H;
    rep(i, 1, N) cin >> w[i] >> h[i];

    rep(i, 0, N + 1) rep(hi, 0, H + 1) dp[i][hi] = infl;
    dp[1][0] = 0;

    rep(i, 1, N) rep(hi, 0, H){
        chmin(dp[i + 1][hi], dp[i][hi]);
        chmin(dp[i + 1][min(H, hi + h[i])], dp[i][hi] + w[i] * i);
    }
    ll ans = infl;
    rep(i, 0, N + 1) chmin(ans, dp[i][H]);
    if (ans == infl) ans = -1;
    cout << ans << endl;
}