ferinの競プロ帳

競プロについてのメモ

KUPC2012 J - 刺身

問題ページ
J: 刺身 - 京都大学プログラミングコンテスト2012 | AtCoder

概要

魚が1匹いてこの魚のi番目(1<=i<=n)の部分の重さはw[i]である。この魚をn個に切り分けたい。区間[l,r]がつながっている部分を一つ選びそのうち一箇所を切断するという操作を繰り返す。この操作には区間[l,r]のw[i]の和のコストがかかる。コストを最小化しろ。

解法

dp[i][j] = ([i,j]を切るのに必要なコスト)としたDPを考える。s番目(i<=s<j)で分割するときのうちもっともよいものを選ぶと考えると、DPの漸化式は dp[i][j] = min_{i<=s<j} (dp[i][s]+dp[s][j]) + sum_{k=i}^{j} w[k] となる。これを愚直に実装するとO(n^3)でTLEだが、コスト関数の部分が単調でQIなのでKnuth-Yao speedupを使うことができO(n^2)で解ける。
MLが結構ぎりぎりなので要注意

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll a[4010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> a[i];

  // Knuth-Yao speedup:X(i,j) = min_{i<=s<j} {X(i,s)+X(s,j)} + W(i,j)
  // time: O(n^2)
  // K(i,j) = argmin_{i<=s<j} (X(i,s) + X(s,j))
  vector<ll> W(n, 0);
  vector<vector<ll>> X(n+1, vector<ll>(n+1, 0));
  VVI K(n+1, VI(n+1, 0));
  W[0] = a[0];
  FOR(i, 1, n) W[i] += W[i-1] + a[i];
  REP(i, n+1) REP(j, n+1) {
    X[i][j] = (i==j ? 0 : LLINF);
    K[i][j] = (i==j ? i : 0);
  }
  for(int w=1; w<=n; ++w) {
    for(int i=0, j=i+w; (j=i+w) < n; ++i) {
      // K(i,j)の単調性から範囲が限定できる
      for(int r = K[i][j-1]; r <= K[i+1][j]; ++r) {
        ll c = X[i][r] + X[r+1][j] + W[j] - (i==0?0:W[i-1]);
        if(X[i][j] > c) { X[i][j] = c; K[i][j] = r; }
      }
    }
  }
  cout << X[0][n-1] << endl;

  return 0;
}