15477 - 水ようかん (Mizuyokan)

작성일 | In

  • 문제 설명

    길이 $L_1+L_2+\cdots+L_N\space(N\leq50, 1\leq L_i\leq1000)$인 막대가 있고, 막대 위 $x=L_1, L_2,\cdots,L_{N-1} $에 각각 막대를 절단할 수 있는 표시가 있습니다. 막대를 적절히 절단하여 최소 막대 길이와 최대 막대 길이간의 길이 차이 $d$를 최소화하는 문제입니다.

  • 해설

    우선 절단한 막대 길이의 하나의 하한을 $lo$로 설정합시다. 이후 막대의 상한 $hi$으로 가능한 값을 parametric search로 찾아줄 수 있습니다. 가능한 $lo$의 값은 최대 $50000$이므로 $O(\sum L\cdot N\log N)$정도에 문제를 해결할 수 있습니다.

  • 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    int n, a[51], dp[51];
  
int f(int l, int r) {
    int ret = a[r];
    if(l) ret -= a[l-1];
    return ret;
}
    
int dfs(int x, int l, int r) {
    int& ret = dp[x];
    if(x == n) return ret = 1;
    if(ret != -1) return ret;
    int sum = 0;
    ret = 0;
    for(int i=x; i<n; i++) {
        if(x == 0 && i == n-1) break;
        sum += a[i];
        if(l<=sum && sum<=r) {
            ret |= dfs(i+1, l, r);
        }
    }
    return ret;
} 
    
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    int mn = *min_element(a, a+n);
    int fans = INF;
    for(int i=mn; i<=50000; i++) {
        int id = 0;
        int l=i, r=50000, ans=INF;
        while(l <= r) {
            int mid = (l+r) / 2;
            memset(dp, -1, sizeof dp);
            if(dfs(0, i, mid)) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        fans = min(fans, ans - i); 
    }
    cout << fans << '\n';
}