Luogu

分析

四边形不等式优化 DP 。

首先有一个显然的 DP :设 $f[i][j]$ 表示前 $i$ 个村庄设了 $j$ 个邮局的最小值,容易得到 $f[i][j]=\min\{f[i-1][j],f[k][j-1]+dis(k+1,i)\}$ 。这里的 $dis(i,j)$ 指 $[i,j]$ 中设一个邮局的最小值。

如果一段区间里要放一个邮局,显然放在中间是最优的。于是可以通过前缀和 $O(n^2)$ 预处理出所有 $dis$ ,然后就可以 $O(n^2m)$ 的 DP 了。

打表可以发现 $f$ 满足四边形不等式,于是就可以优化到 $O(nm)$ 了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10,M=300+10;

int n,m,a[N];
int s[N][N],dis[N][N],f[N][M],p[N][M];

int main() {
    memset(f,0x3f,sizeof(f));
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;++j) s[i][j]=s[i][j-1]+a[j];
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;++j) {
            int mid=(i+j)>>1;
            dis[i][j]=(mid-i)*a[mid]-s[i][mid-1]
                     +s[mid+1][j]-(j-mid)*a[mid];
        }
    for (re int i=1;i<=n;++i) f[i][1]=dis[1][i];
    for (re int j=2;j<=m;++j) {
        p[n+1][j]=n;
        for (re int i=n;i;--i)
            for (re int k=p[i][j-1];k<=p[i+1][j];++k)
                if (f[k][j-1]+dis[k+1][i]<f[i][j])
                    f[i][j]=f[k][j-1]+dis[k+1][i],p[i][j]=k;
    }
    printf("%d\n",f[n][m]);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 16 PM