Description
There are $N$ villagers (including the village chief) living in Number Village. Interestingly, all of their houses lie on a straight line. The house of the $i$-th villager $(0 ≤ i < N)$ lies exactly $a_i$ kilometers to the east of the village chief’s house. (For simplicity, the $0$-th villager is the village chief, so $a_0 = 0$.)Recently, a tournament is going to be held in Number Village, in which everyone in the village will participate. For the convenience of villagers, the organizer plans to build K stadiums. The stadium can be built anywhere in the village, even at the same place as any villager’s house.However, the organizer wants the traffic cost to be minimized. The traffic cost is defined by $\sum_{i=0}^{N-1}\min_{j=0}^{K-1}D(a_i,s_j)$, where $D(a_i, s_j)$ is the distance between the $i$-th villager’s house and the $j$-th stadium.Your task is to calculate the minimal traffic cost (rounded down to the nearest integer), given $N, K$ and $a_i$.
Idea
考虑一个这样的 $DP$。设 $dp_{i,j}$ 表示前 $i$ 个村庄，建立了 $j$ 个车站的最小代价。每次转移枚举上一个位置，并将车站建立在区间 $[a_j , a_i]$ 的 $a_{mid}$ 处，这样一定是最优的。直接转移，复杂度为 $\Theta(n^3)$。
注意到这个 $DP$ 具有这样一个性质，随着我们加入的车站越来越多，总代价一定是减少得越来越少的。于是我们可以用 WQS 二分优化。复杂度降至 $\Theta(n^2 \log n)$。
继续分析转移。我们还能发现，我们设 $f_{l,r}$ 表示 $[l, r]$ 这个区间内建立一个车站，区间的最小代价。则 $f_{l,r}= sum_{l−1} + sum_r − sum_{\frac{l+r−1}{2}}− sum_
{\frac{l+r}{2}}$。
由上式，对于 $a < b < c < d$，我们可以得到
$$f_{a,c}+f_{b,d}\leq f_{a,d}+f_{b,c}$$
假设 $i’$ 这个点是从 $j’$ 转移过来的，$i$ 这个点是从 $j$ 转移过来的，且 $i’ < i$，那么我们就会有：
$$dp_{j’}+f_{j’+1,i’}\leq dp_j + f_{j+1,i’}$$
$$dp_{j’}+f_{j’+1,i}\geq dp_j + f_{j+1,i}$$
利用上面关于 $f$ 的不等式，我们可以得到 $j’\leq j$。
于是这个 $DP$ 的决策具有单调性，因此可以继续进行优化，利用一个队列维护决策点，进行决策单调性优化即可。最终的复杂度是 $\Theta(n\log^2 n)$。
Code
#include <bits/stdc++.h>
#define ll long long
#define maxn 1000100
int a[maxn],n,m;
ll sum[maxn],dp[maxn];
int nxt[maxn],que[maxn],tim[maxn];
ll Cal(int l,int r){
int mid=((l+r+1)>>1),flag=((r-l+1)&1);
return sum[r]-sum[mid]-(a[mid]*flag)-sum[mid-1]+sum[l];
}
bool Check(int i,int j,int k){
ll val1=dp[i]+Cal(i,k),val2=dp[j]+Cal(j,k);
if (val1==val2) return tim[i]<tim[j];
return val1<val2;
}
int Solve(ll val){
memset(dp,0x3f,sizeof(dp));
memset(tim,0,sizeof(tim));
int h=1,t=1;
que[h]=dp[0]=0,nxt[h]=1;
for (int i=1;i<=n;++i){
while(h<t&&nxt[h+1]<=i) h++;
dp[i]=dp[que[h]]+Cal(que[h],i)+val;
tim[i]=tim[que[h]]+1;
while(h<=t&&Check(i,que[t],nxt[t])) t--;
int l=nxt[t],r=n+1;
while(l<r){
int mid=((l+r)>>1);
if (Check(i,que[t],mid)) r=mid;
else l=mid+1;
}
if (l<=n) que[++t]=i,nxt[t]=l;
}
return tim[n];
}
int main(){
freopen("station.in","r",stdin);
freopen("station.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
scanf("%d",a+i),sum[i]=sum[i-1]+a[i];
ll l=0,r=sum[n]+1;
while(l<r){
ll mid=((l+r)>>1);
if (Solve(mid)<=m) r=mid;
else l=mid+1;
}
Solve(l);
printf("%lld\n",dp[n]-l*m);
}