[JOI精進録] 難易度7「水ようかん」(JOI2017/2018 予選D)

問題リンク

atcoder.jp

問題概要

水ようかんを指定された場所から何箇所か選んで切る。
最大の大きさと最小の大きさの差を最小化してください。

解説

AC解法 (100/100点)

最小値を全探索し、
個目の切れ目までを考えたときの最大の大きさの最小値
との差の最小値を求めればよいです。

ACコード

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

int main(){
#define int long long
  int n,t; cin >> n;
  vector<int> acc(n+1); for (int i(0);i < n;++i) (cin>>t),acc[i+1]=acc[i]+t;
  auto f = [&n,&acc](const int x){
    vector<int> dp(n+1,numeric_limits<signed>::max()); dp[0] = 0;
    for (int i(0);i < n;++i){
      for (int k(i+1);k <= n;++k){
        if (acc[k]-acc[i]<x) continue;
        if (i==0&&k==n) continue;
        dp[k] = min(dp[k],max(dp[i],acc[k]-acc[i]));
      }
    }
    return dp[n];
  };
  int r = f(0);
  for (int i(1);i < acc.back();++i) r = min(r,f(i)-i);
  cout << r << endl;
}

提出結果

atcoder.jp