いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK！

問題概要

直線上にカツが $N$ 個ある。 $i$ 個目のカツは位置 $X_i$ にあり、その重さは $W_i$ である。これらのカツを、次のようにしてすべて回収する。

直線上に 2 点 A, B を配置する (コスト 1)。配置した点上にカツがあるならば、カツを回収する
2 点を動かしていく。距離 1 動かすのに要するコストは、1 + (回収したカツの重さの総和) となる
2 点が一致したら、コスト $K$ を支払って 2 点を回収する

すべてのカツを回収するのに要するコストの最小値を求めよ。

制約

$1 \le N \le 2000$

考えたこと

一回の操作で回収するコストは連続する区間になる。よって、区間ごとに分割するタイプの DP で解けそう。つまり、

${\rm dp} \lbrack i \rbrack$ := 区間 $\lbrack 0 : i)$ のカツをすべて回収する最小コスト

として、

${\rm dp} \lbrack i \rbrack$ = $\min_{0 \le j \lt i} ({\rm dp} \lbrack j \rbrack + f(j, i-1))$

という感じで行ける。ここで $f(l, r)$ は、A をカツ $l$ に、B をカツ $r$ に配置したときに、カツ $l, l+1, \dots, r$ をすべて回収するための最小コストとする。

f(l, r) を求める

よって、区間 $\lbrack l, r)$ のカツをすべて回収するのに必要なコストを計算する問題へと帰着された。

2 点 A, B をどこで合流させるかを考えることになる。基本的には、カツがあるところに合流させればよい。よって、 $k = l, l+1, \dots, r-1$ のいすれかのカツのところで 2 点 A, B を合流させる。つまり、

カツ $x$ から右へと移動してカツ $y$ まで移動するのにかかるコストを $g(x, y)$
カツ $y$ から左へと移動してカツ $x$ まで移動するのにかかるコストを $h(x, y)$

と表すと、 $f(x, y) = \min_{k = x, x+1, \dots, y}(g(x, k) + h(k, y))$ となる。そして少し考えると、

$x$ を固定したとき、 $f(x, y)$ を最小にするような $k$ は $y$ に対して単調増加

ということがいえる。よって、しゃくとり法を用いることで、 $f(l, r)$ テーブル全体を求めるのに要する計算量は $O(N^{2})$ になる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N, K;
vector<long long> X, W;
long long solve() {
    vector<vector<long long>> cost(N+1, vector<long long>(N+1, 0));
    vector<long long> sumW(N+1, 0), sum(N+1, 0);
    for (int i = 0; i < N; ++i) {
        sumW[i+1] = sumW[i] + W[i];
        sum[i+1] = sum[i] + sumW[i+1] * (X[i+1] - X[i]);
    }

    auto g = [&](int l, int r) {
        return sum[r] - sum[l] - sumW[l] * (X[r] - X[l]);
    };
    auto h = [&](int l, int r) {
        return (sumW[r+1] - sumW[l]) * (X[r] - X[l]) - g(l, r);
    };
    auto f = [&](int l, int r, int k) {
        return g(l, k) + h(k, r);
    };

    for (int l = 0; l < N; ++l) {
        int k = l;
        for (int r = l; r < N; ++r) {
            while (k < r && f(l, r, k) > f(l, r, k + 1)) ++k;
            cost[l][r] = f(l, r, k) + (X[r] - X[l]) + K + 1;
       }
    }

    vector<long long> dp(N+1, 1LL<<60);
    dp[0] = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < i; ++j) {
            chmin(dp[i], dp[j] + cost[j][i-1]);
        }
    }
    return dp[N];
}

int main() {
    cin >> N >> K;
    X.assign(N+1, 0), W.assign(N+1, 0);
    for (int i = 0; i < N; ++i) cin >> X[i] >> W[i];
    cout << solve() << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3178 Katsusando (HUPC 2020 day3-G)

問題概要

制約

考えたこと

f(l, r) を求める