[LUOGU] P4767 [IOI2000]邮局

https://www.luogu.org/problemnew/show/P4767

四边形不等式好题!

可以设f[i][j]表示前i个村庄，建了j个邮局的最小代价。

转移：f[i][j]=min{f[k][j-1]+dis[k+1][i]}

也就是枚举断点，断点后整个区间建造一个邮局并强制整个区间都选择它。

这个邮局在哪里最优呢？由人类智慧知，在中位数处最优。

注意到这样的转移下，时间复杂度是O(m*n^2)的，不行

这是一个前缀问题，但是同时它也是一个区间问题，回忆四边形不等式的形式，尝试套上去

至此，我们就有了O(nm)的优秀做法。

（证明暂时不会，有会证明的欢迎留言..）

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

inline int rd(){

  int ret=,f=;char c;

  while(c=getchar(),!isdigit(c))f=c=='-'?-:;

  while(isdigit(c))ret=ret*+c-'',c=getchar();

  return ret*f;

}

const int MAXN=;

int n,m;

int val[MAXN],sum[MAXN],dis[MAXN][MAXN];

int f[MAXN][],tran[MAXN][];

int main(){

  memset(f,0x3f,sizeof(f));

  n=rd();m=rd();

  for(int i=;i<=n;i++) val[i]=rd();

  sort(val+,val++n);

  for(int i=;i<=n;i++) sum[i]=sum[i-]+val[i];

  for(int i=;i<=n;i++)

    for(int j=i+;j<=n;j++)

      dis[i][j]=dis[i][j-]+val[j]-val[i+j>>];

  for(int i=;i<=n;i++) f[i][]=dis[][i];

  int mn=<<,mnid;

  for(int j=;j<=m;j++){

    tran[n+][j]=n-;

    for(int i=n;i>=j;i--){

      for(int k=tran[i][j-];k<=tran[i+][j];k++){

        if(f[k][j-]+dis[k+][i]<f[i][j]){

          f[i][j]=f[k][j-]+dis[k+][i];

          tran[i][j]=k;

        }

      }

    }

  }

  cout<<f[n][m];

  return ;

}