给出一个长度为n序列({a_i})，将其划分成连续的K段，对于其中一段([l,r])，设其中位数为m，定义其权值为(sum_{i=l}^r|m-a_i|)，求最小的权值之和,(nleq 2000,Kleq 25)。
解
显然设(f[i][j])表示前i个数划分成j段的的最小权值和，设(m(i,j))为(isim j)的作为一段的权值，所以有
[f[i][j]=min_{0leq k<i}{f[k][j-1]+m(k+1,i)}
]
边界：(f[0][0]=0)，其余无限大
答案：(f[n][K])
注意到时间复杂度(2000^2 imes 25=10^8)，为一亿，可以险过，关键在于快速求二元函数m，而求m需要解决的是动态维护一段序列中中间大的数，显然中位数的位置是递增的，可以考虑双堆堆顶优化，不难得知对于序列(b_1,b_2,...,b_p)而言设其中位数为(b_q)，于是有权值为
[sum_{i=1}^p|b_i-b_q|=|b_p-b_q|+...+|b_q-b_q|+...+|b_q-b_1|=
]
[=b_p-b_q+..+b_q-b_q+...+b_q-b_1=(b_p+...+b_{q+1})-(b_q+...+b_1)+qb_q-(p-q)b_q=
]
[sum_{i=q+1}^pb_i-sum_{i=1}^qb_i+(2q-p)b_q
]
于是对于权值，我们只要维护这样一个式子即可，步骤如下
- 枚举左端点i，设大根堆为H，小根堆为E
- 初始化(m(i,i)=0,k=-a_i)，H加入(a_i)
- 枚举右端点j
- 如果(a_jleq H.top())，那么(E.push(H.top()),H.pop(),k+=E.top() imes 2,H.push(a_j),k-=a_j)
- 否则(E.push(a_j),k+=a_j)
- 如果(i-j+1)为偶数的话，那么(H.push(E.top()),E.pop(),k-=H.top() imes 2)
- 计入答案(m(i,j)=k+(2q-p) imes H.top())
参考代码：
#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
#include <cstring>
#define il inline
#define ri register
#define intmax 0x7fffffff
using namespace std;
int a[2001],m[2001][2001],dp[2001][26];
priority_queue<int,vector<int>,less<int> >H;
priority_queue<int,vector<int>,greater<int> >E;
il void read(int&);
int main(){
int n,K;
while(read(n),read(K),n&&K){
for(int i(1);i<=n;++i)read(a[i]);
for(int i(1),j,k;i<=n;++i){
while(H.size())H.pop();
while(E.size())E.pop();
H.push(a[i]),k=-a[i];
for(j=i+1;j<=n;++j){
if(a[j]<=H.top())
E.push(H.top()),H.pop(),H.push(a[j]),
k-=a[j],k+=E.top()<<1;
else E.push(a[j]),k+=a[j];
if((j-i+1)&1)k-=E.top()<<1,H.push(E.top()),E.pop();
m[i][j]=k+H.top()*((H.size()<<1)-(j-i+1));
}
}memset(dp,2,sizeof(dp)),dp[0][0]=0;
for(int i,j(1),k;j<=K;++j)
for(i=j;i<=n;++i)
for(k=0;k<i;++k)
if(dp[i][j]>dp[k][j-1]+m[k+1][i])
dp[i][j]=dp[k][j-1]+m[k+1][i];
printf("%d
",dp[n][K]);
}
return 0;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c==' '||c=='
'||c=='
');
ri bool check(false);if(c=='-')check|=true,c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(check)x=-x;
}