题目概述

有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。

解题报告

显然是 $O(n^2m)$ DP吧？数据小的可怜，这样就可以过了……

不过有一种更好的方法，可以把 $m$ 优化到 $log_2m​$ ，这就是wqs(%%%Orz)二分了。

想法是这样的：去掉 $f[i][j]$ (前 $i$ 个村庄中建了 $j$ 个邮局)中的 $j$ ，枚举一个 $cost$ 表示建邮局需要额外的 $cost$ 花费，再记录一个 $g[i]$ 表示前 $i$ 个村庄在最优解的情况下最少建多少邮局。接下来刷DP，如果 $g[n]\le m$ 就说明可行。由此可见 $cost$ 是可以二分枚举的，所以我们就可以愉快的把 $O(n^2m)$ 优化成 $O(n^2log_2m)$ 。

严格的来说，只有当原函数 $g(x)$ 的斜率单调，才可以这么处理。因为枚举 $cost$ 实际上是一个逼近 $g(x)$ 斜率的过程 $[g(x)-x\cdot cost]'=g'(x)-cost$ ，如果 $g'(x)$ 不是单调的，就没办法二分枚举 $cost$ 了。

还有要注意的是，最后并不一定刚好停在 $m$ 个的位置，因为最优答案可能有一段相同。所以算答案的时候不能用 $f[n]-g[n]\cdot cost$ ，一定要用 $f[n]-m\cdot cost$ 。

另一道经典的wqs二分是BZOJ2654，那时候说这二分怎么这么神奇，原来是wqs二分QAQ。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=300;

int n,m,dis[maxn+5],pre[maxn+5][maxn+5],suf[maxn+5][maxn+5],w[maxn+5][maxn+5];
int f[maxn+5],g[maxn+5];

inline void Fix(int fj,int gj,int &fi,int &gi) {if (fj<fi||fj==fi&&gj<gi) fi=fj,gi=gj;}
inline bool check(int cst){
    memset(f,63,sizeof(f));f[0]=0;g[0]=0;
    for (int i=1;i<=n;i++)
        for (int j=0;j<i;j++)
            Fix(f[j]+w[j+1][i]+cst,g[j]+1,f[i],g[i]);
    return g[n]<=m;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&dis[i]);
    for (int i=1;i<=n;i++) for (int j=i;j;j--) pre[j][i]=pre[j+1][i]+dis[i]-dis[j];
    for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) suf[i][j]=suf[i][j-1]+dis[j]-dis[i];
    for (int i=1,k;i<=n;i++)
        for (int j=(k=i);j<=n;j++)
            w[i][j]=pre[i][i+j>>1]+suf[i+j>>1][j];
    int L=0,R=dis[n]*n;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) check(mid)?R=mid-1:L=mid+1;
    return check(L),printf("%d\n",f[n]-m*L),0;
}