[AOJ] No. 0644 水ようかん (Mizuyokan)

2019年11月11日

問題

方針

最小値を固定

水ようかんを切り分けた時の長さの値は、切る箇所を任意の \( 2 \) 点選ぶことを考えると、最大でも

\[\dfrac{N(N + 1)}{2} – 1\]

あることが分かります。したがって、最小値を固定したときの、最大値を変数とみて、最大値の最小値を求めます。

動的計画法

水ようかんのピースの最小値を \( l \) と固定して動的計画法を行います。このとき、\( d_i \) を \( i \) 番目の切れ目まで調べたのピースの最大値の最小値とします。初期値は、\( d_i = 0 \) とし、それ以外は、\( d_i = \infty \) とします。また、更新後の配列は \( l \leq d_i \ ( i \neq 0 )\) を満たす必要があります。

配列の更新は、\( i \) 番目の切れ目から先頭に向かって連結させていきます。このときのピースの長さを \( t \) とします。\( 0 \leq j \leq i \) となる \( j \) について、\( l \leq t \) のとき、

\[d_{i + 1} = \min(d_{i+1}, \max(d_j, t))\]

となります。\( j \) について、\( i \) から \( 0 \) へと更新していきます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
int L[50]{};
int a[51]{}; // 累積和
int ans = INT32_MAX;

int dp[51]{};

void solve(int l) {
    fill(dp, dp + 51, 100000000);
    
    dp[0] = 0;
    for (int i = 0; i < N; i++) {
        int t = 0;
        for (int j = i; j >= 0; j--) {
            t += L[j];
            // 水ようかん全てを連結したものは除外する
            if(i == N - 1 && j == 0) continue;
            if (t >= l) {
                dp[i + 1] = min(dp[i + 1], max(dp[j], t));  
            }
        }
    }
    ans = min(ans, dp[N] - l);
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> L[i];
    }
    for (int i = 0; i < N; i++) {
        a[i + 1] += a[i] + L[i];
    }
    set<int> s;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j <= N; j++) {
            s.insert(a[j] - a[i]);
        }
    }
    
    // 水ようかんの全体の長さは除外
    s.erase(*s.rbegin());
    for (int i : s) {
        solve(i);
    }
    cout << ans << "\n";
    return 0;
}