P6246 [IOI2000] 邮局 加强版 加强版
gxy001
·
·
题解
本文为 O(n\log V) 的 wqs 二分+斜率优化做法。
下面这段仅用于凸性的证明，与做法无关：
设 w(l,r) 表示在 \lfloor\frac{l+r}{2}\rfloor 处建立邮局，l 到 r 的村庄全部去往该邮局的距离之和，则有 dp 式子：
f_{i,j}=\min_{0\le t<i}\{f_{t,j-1}+w(t+1,i)\}
由于 w(l,r) 满足四边形不等式，则 ans_m=f_{n,m} 是关于 m 的凸函数，这一经典结论的证明参见此处。
进行 wqs 二分，消去 m 的限制，二分的斜率为 K。
关于 K 的二分范围，这个凸包是单调减的下凸壳，考虑 0\ge ansK=ans_{m+1}-ans_m\ge ans_{n}-ans_m=-ans_m，由题目的保证知道 ans_m\le 10^9，所以二分范围取 [-10^9,0] 即可。
设 f_i 为已经考虑完了前 i 个村庄的最小代价（s 为 a 的前缀和），我们有：
f_i=\min_{1\le j\le i}\{(s_i-s_j)-(i-j)a_j+\min_{0\le k<j}\{(j-k)a_j-(s_j-s_k)+f_k\}\}-K
令 g_j=\min_{0\le k<j}\{(j-k)a_j-(s_j-s_k)+f_k\}，g 可以用斜率优化得到。
都是经典的斜率优化形式，具体做法就不加赘述了。
另外，提醒一下 wqs 二分时记得处理斜率相同的段。
```cpp
#include<iostream>
using std::cin,std::cout;
int n,m;
long long a[500010],s[500010],f[500010],g[500010],cntf[500010],cntg[500010];
int check(long long K){
auto x1=[](int x){return x;};
auto y1=[](int x){return s[x]+f[x];};
auto x2=[](int x){return a[x];};
auto y2=[](int x){return -s[x]+x*a[x]+g[x];};
f[0]=0,cntf[0]=0;
static int q1[500010];
int *hd1=q1,*tl1=q1;
*tl1++=0;
static int q2[500010];
int *hd2=q2,*tl2=q2;
for(int i=1;i<=n;i++){
while(tl1-hd1>1){
if(std::pair(y1(*hd1)-a[i]*x1(*hd1),cntf[*hd1])<std::pair(y1(hd1[1])-a[i]*x1(hd1[1]),cntf[hd1[1]])) break;
else ++hd1;
}
cntg[i]=cntf[*hd1];
g[i]=i*a[i]-s[i]+y1(*hd1)-a[i]*x1(*hd1);
while(tl2-hd2>1){
if(std::pair((y2(i)-y2(tl2[-1]))*(x2(tl2[-1])-x2(tl2[-2])),cntg[i])>std::pair((y2(tl2[-1])-y2(tl2[-2]))*(x2(i)-x2(tl2[-1])),cntg[tl2[-1]])) break;
else --tl2;
}
*tl2++=i;
while(tl2-hd2>1){
if(std::pair(y2(*hd2)-i*x2(*hd2),cntg[*hd2])<std::pair(y2(hd2[1])-i*x2(hd2[1]),cntg[hd2[1]])) break;
else ++hd2;
}
cntf[i]=cntg[*hd2]+1;
f[i]=-K+s[i]+y2(*hd2)-i*x2(*hd2);
while(tl1-hd1>1){
if(std::pair((y1(i)-y1(tl1[-1]))*(x1(tl1[-1])-x1(tl1[-2])),cntf[i])>std::pair((y1(tl1[-1])-y1(tl1[-2]))*(x1(i)-x1(tl1[-1])),cntf[tl1[-1]])) break;
else --tl1;
}
*tl1++=i;
}
return cntf[n];
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=a[i]+s[i-1];
int l=-1e9,r=0;
long long ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)<=m) l=mid+1,ans=mid;
else r=mid-1;
}
check(ans);
cout<<f[n]+m*ans<<'\n';
return 0;
}
```