题解：P4767 [IOI2000] 邮局 加强版

· · 题解

摘要：本文将介绍一种 决策单调性分治 做法。

首先有一个 dp，设 f(i,j) 表示考虑到前缀 [1,i] 已经放了 j 个邮局的答案，则不难有转移：

f(i,j)=\min_{k=0}^{i-1}f(k,j-1)+w(k+1, i)

其中 w 是一个可以 O(V^2) 递推的一个玩意。

观察这个转移式，可以按照 j 分层，f(,j) 之间不会影响，而只有 f(,j-1) 才会对 f(,j) 产生直接的影响。于是可以考虑依次求出每一层的答案。

由于 w 满足四边形不等式，所以我们可以分治求出每一层的 dp 值。

具体来说，假设现在分治到区间 [l,r]，设 m 为区间中点，目前最优决策点位于 [L,R]，则我们可以暴力求出 m 的决策点 p，然后 [l,m-1] 的决策点一定位于 [L,p]，[m+1,r] 的决策点一定位于 [p,R]，规模得到缩减，于是我们可以继续分治。

时间复杂度 O(VP\log P)。

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

const int N = 3e3 + 5;
int n, m, a[N], f[N], g[N], w[N][N];

void solve(int l, int r, int L, int R){
    if(l > r) return;
    int mid = (l + r) >> 1, s = L;
    auto wgt = [&](int k, int i){ return g[k] + w[k + 1][i]; };
    for(int i=L;i<=min(R, mid - 1);i++){
        if(wgt(i, mid) < wgt(s, mid)) s = i;
    }
    f[mid] = wgt(s, mid);
    solve(l, mid - 1, L, s);
    solve(mid + 1, r, s, R);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            w[i][j]=w[i][j-1]+a[j]-a[(i+j)>>1];
        }
    }
    for(int i=1;i<=n;i++) f[i] = w[1][i];
    for(int i=2;i<=m;i++){
        copy(f + 1, f + n + 1, g + 1);
        solve(1, n, 1, n);
    }
    cout << f[n] << '\n';
    return 0;
}

// Written by xiezheyuan