力持ち [パソコン甲子園2014 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0303?year=2014

前提知識

• 区間DP

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0303/judge/3162012/C++14

二段階でDPして解く。
　
まず、区間DPをする。
can[L][R] := [L,R]を1つにすることができるか
幅が小さい方から確定させていく。
can[L][R]が1になるかは、

• [L,R-1]を1つにして、それをR番目が担ぐ
• [L+1,R]を1つにして、それをL番目が担ぐ

のどちらかである。
　
次に、普通のDPをする。
dp[i] := i番目まででまとめることのできるグループの最小数
1つにできるグループを全探索して、もらうDPによって遷移を実現する。

int N, C[1010], W[1010];
int can[1010][1010]; int dp[1010];
//---------------------------------------------------------------------------------------------------
int sm[1010];
int get(int a, int b) { // [a,b]
    int res = sm[b];
    if (a) res -= sm[a - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> C[i] >> W[i];

    sm[0] = W[0];
    rep(i, 1, N) sm[i] = sm[i - 1] + W[i];

    rep(i, 0, N) can[i][i] = 1;
    rep(len, 2, N + 1) rep(L, 0, N - len + 1) {
        int R = L + len - 1;

        if (get(L, R - 1) <= C[R] and can[L][R-1]) can[L][R] = 1;
        if (get(L + 1, R) <= C[L] and can[L + 1][R]) can[L][R] = 1;
    }

    rep(i, 0, N) dp[i] = inf;
    dp[0] = 0;

    rep(i, 0, N) {
        dp[i] = inf;
        rep(j, 0, i + 1) if (can[j][i]) {
             if(j) chmin(dp[i], dp[j - 1] + 1);
             else chmin(dp[i], 1);
        }
    }

    cout << dp[N - 1] << endl;
}