P10967
设在 \(1\sim i\) 装了 \(j\) 个邮局的答案 \(f_{i,j}\)：\(f_{i,j}=\min\{f_{k,j-1}+w_{k+1,i}\}\)，其中 \(w_{l,r}\) 为 \(l\sim r\) 有一个邮局的最小距离。
- \(w_{l,r}\) 怎么求？在中位点装邮局。那么有 \(w_{l,r}=w_{l,r-1}+x_j-x_{[(i+j)/2]}\)。其中 \(x\) 是村庄位置。进一步有 \(\mathcal{O}(1)\) 算法，\(m=[(l+r)/2],w_{l,r}=x_{m}\times (2m-l-r-1)+sum_{l+1}+sum_r-2sum_m\)。所以这个不是复杂度瓶颈。
得到了一个 \(\mathcal{O}(v^2p)\) 的算法。
P4767
\(f_{i,j}=\min\{f_{k,j-1}+w_{k+1,i}\}\) 这个方程内，状态较难优化，所以尝试优化转移。
证：\(w_{l,r}\) 符合 \(Q.I.\)。
\(w_{i,j}+w_{i',j'}\le \sum_{l=i}^j |d_l-d_z|+\sum_{l=i'}^{j'}|d_l-d_y|\)。
\(\le \sum_{l=i}^j |d_l-d_z|+\sum_{l=i'}^{j'}|d_l-d_y|+\sum_{l=j+1}^{j'}|d_l-d_z|-\sum_{l=j+1}^{j'}|d_l-d_y|\)。
\(=\sum_{l=i}^{j'}|d_l-d_z|+\sum_{l=i'}^j |d_l-d_y|=w(i,j')+w(i',j)\)。
令 \(m_{i,j}\) 为 \(f_{i,j}\) 最小决策点。
引理 \(1\)：\(m_{i+1,j}\ge m_{i,j}\)。
引理 \(2\)：\(m_{i,j-1}\le m_{i,j}\)。
计算 \(m_{i,j-1}\le k\le m_{i+1,j}\)。从小到大枚举 \(j\)，从大到小枚举 \(i\) 即可。
时间复杂度 \(\mathcal{O}(pv)\)。
P6246
尝试优化状态！这个“邮局数量”状态让人联想起 wqs 二分。
或者感性理解：如果每建立一个邮局有一个附加的费用，费用越高你想要建立的邮局数量就会减少。所以是一个上凸包。
二分 \(mid\) 费用，就变成了：\(f_{i}=\min\{f_{k}+w_{k+1,i}+mid\}\)。这个是 1D-1D dp 方程。
\(f(i)=\min_{0\le j<i} f(j)+w(j,i)\)。（注意是 \(\min\)！）组数没有限制的分组问题。
定理：若 \(w\) 符合 \(Q.I.\)，当 \(d\ge c\) 时，\(f(d)\) 的最优决策点 \(\ge f(c)\) 最优决策点。
因此：对于每个已经计算出来的 \(f_i\)，去寻找它能更新的状态有哪些。在栈顶的决策起始位置判断起始位置是否决策 \(i\) 更优。如果是，则退栈，继续执行，否则，二分决策位置。
最终代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5+5;
struct node {
ll l,r,x;
} stk[N];
ll n,m,a[N],sum[N],dp[N],top,cnt[N];
ll w(ll l,ll r){
ll mid=(l+r+1)/2;
return a[mid]*(mid+mid-l-r)+sum[l]+sum[r]-sum[mid]*2;
}
int ff(int i){
int l=stk[top].l-1,r=stk[top].r+1;
while (l+1<r){
int mid=l+r>>1;
if (dp[i]+w(i,mid)<=dp[stk[top].x]+w(stk[top].x,mid)){
r=mid;
}
else{
l=mid;
}
}
return r;
}
bool chk(ll x){
top=1;
stk[1]={1,n,0};
for (int i=1,cur=1; i<=n; i++){
dp[i]=dp[stk[cur].x]+w(stk[cur].x,i)+x;
cnt[i]=cnt[stk[cur].x]+1;
while (i<stk[top].l && dp[i]+w(i,stk[top].l)<=dp[stk[top].x]+w(stk[top].x,stk[top].l)){
top--;
}
int pos=ff(i);
stk[top].r=pos-1;
if (pos<=n){
stk[++top]={pos,n,i};
}
if (i==stk[cur].r){
cur++;
}
}
return cnt[n]>=m;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for (int i=1; i<=n; i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
ll l=-1,r=1e9;
r++;
while (l+1<r){
ll mid=l+r>>1;
if (chk(mid)){
l=mid;
}
else{
r=mid;
}
}
chk(l);
cout<<dp[n]-l*m<<"\n";
return 0;
}