说在前面
都是一些 OI Bingo 上的题，可能还会有部分 ABC 的题。
P5929 [POI1999] 地图
题目大意
将一个长度为 \(N\) 的序列染成 \(M\) 种颜色。
对于一个颜色 \(k\)，要求染 \(k\) 颜色的点权与 \(A(k)\) 的差的绝对值尽量地小。
其中 \(A(k)\) 定义如下：
- 在染颜色 \(k\) 的点中至少有一半的点的权值不大于 \(A(k)\)。
- 在染颜色 \(k\) 的点中至少有一半的点的权值不小于 \(A(k)\)。
求最小误差。
解题思路
首先看到这个 \(A(k)\)，这个是什么？
考虑直接将 \(a\) 升序排序，令染颜色 \(k\) 的最小的点下标为 \(l\)，最大的点下标为 \(r\)。
那么 \(a_{\frac {l+r}{2}}\) 就是 \(A(k)\)。
考虑 dp，设 \(f_{i,j}\) 表示前 \(i\) 个数中用 \(j\) 种颜色染色的最小误差。
记 \(l\) 与 \(r\) 之间的误差为 \(calc(l,r)\)，就可以得到状态转移：
\(f_{i,j} = \min _{k=1}^{i} f_{k-1,j-1} + calc(k,i)\)。
如何在 \(O(1)\) 内求出 \(calc(l,r)\)？
令 \(md = \frac {l+r}{2}\)。
\(calc(l,r) = \sum _{i=md+1}^{r} a_i-a_{md} + \sum _{i=l}^{md-1} a_{md}-a_i\)。
将 \(a_{md}\) 全部提取出来，就可以得到：
\(calc(l,r) = \sum _{i=md+1}^{r} a_i -(r-md) \times a_{md} +(md-l) \times a_{md} - \sum _{i=l}^{md-1} a_i\)。
注意到 \(\sum _{i=md+1}^{r} a_i\) 和 \(\sum _{i=l}^{md-1} a_i\) 都可以用前缀和解决，那么这道题就做完了，最终答案为 \(f_{n,m}\)。
程序时间复杂度 \(O(N^2 \times M)\)。
计算 \(calc\) 部分：
int calc(int l,int r){
int md=(l+r)>>1;
int sum1=sum[r]-sum[md];
int sum2=sum[md-1]-sum[l-1];
int m1=a[md]*(r-md),m2=a[md]*(md-l);
return sum1-m1+m2-sum2;
}
状态转移部分：
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=i;k++){
f[i][j]=min(f[i][j],f[k-1][j-1]+calc(k,i));
}