题解：AT_abc355_g [ABC355G] Baseball
违规用户名1271019
·
·
题解
做一个简化 LARSCH 板子题。
题目需要我们算：
\sum_{i=1}^{n}P_i\times\min_{j=1}^K|i-x_j|
考虑每一段数之间的贡献，钦定 x_0 为负无穷小，x_{K+1} 为正无穷大，容易转化成：
\sum_{i=1}^{K+1} \sum_{x_{i-1}<j<x_i} P_j\times\min(j-x_{i-1},x_i-j)
我们令：
\operatorname W(l,r)=\sum_{i=l}^r P_i\times\min(j-l+1,r+1-i)
设 f_{i,j} 为前 i 个数选了 j 个 x 的最小代价。转移有：
f_{i,j}=\min_{k=1}^{i-1}f_{k,j-1}+\operatorname W(k+1,i-1)
注意到 $\operatorname W(l,r)$ 是满足四边形不等式的。打表验证猜想。
::::info[打表代码]
```cpp
mt19937_64 rnd(time(0));
void Solve(int Ti=0) {
n=2000;
rep(i,1,n) p[i]=rnd()%(N*N);
rep(i,1,n) rep(j,i,n) rep(k,i,j) w[i][j]+=min(k-i,j-k)*p[k];
rep(a,1,n) rep(b,a,n) rep(c,b,n) rep(d,c,n) if(w[a][c]+w[b][d]>w[a][d]+w[b][c]) cout << "No\n";
return;
}
```
发现它什么都没有输出。
::::
四边形不等式优化就有 $\mathcal{O}(nk)$。不重要。
考虑正解。注意到 $f_n$ 是单调的，因为多选几个点是不劣的。由于有决策单调性，我们使用简化 LARSCH 算法。
先 wqs 二分，把转移变成：
$$
f_i=\min_{k=1}^{i-1}f_k+\operatorname W(k+1,i-1)+x
$$
其中 $x$ 是 wqs 二分的数。剩下的直接[在线分治](https://www.luogu.com.cn/article/vqf42hah)即可。