https://vjudge.net/problem/HDU-4261
对于一个长2000的数列划分最多25个块,每块代价为块内每个数与块内中位数差的绝对值之和,求最小总代价。
套路化地,设$f[i][j]$表示第$i$位,划了$j$块最小代价。然后dp。$O(n^3k)$不必说。($logn$和$k$看成同数量级,其实是$O(n^3(k+logn))$)
然后重点在于找中位数。上述暴力浪费在于每段区间中位数都要寻找一遍。可以用对顶堆(其实是不想写平衡树,或者不会更优秀,码量更小的玩意儿了),动态维护中位数,不多说了。求代价就是对两个堆总和记$s1,s2$,配合中位数即可算出,每算出一段的代价就顺便转移。
然后就$O(n^2k)$了。
不知道为什么跑那么快,直接在hdu屠榜rk1了。。qwq
Upd:被2人超过了。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define _dbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=+;
ll f[N][],s1,s2,res;
int a[N];
int n,m;int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
while(read(n),read(m),n||m){
for(register int i=;i<=n;++i)read(a[i]);
memset(f,0x01,sizeof f);f[][]=;
for(register int i=;i<n;++i){
priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int> > q2;
s1=s2=res=;
for(register int j=i+;j<=n;++j){
if(q1.empty()||a[j]<=q1.top())q1.push(a[j]),s1+=a[j];else q2.push(a[j]),s2+=a[j];
while(q1.size()>q2.size()+)s1-=q1.top(),s2+=q1.top(),q2.push(q1.top()),q1.pop();
while(q2.size()>q1.size())s2-=q2.top(),s1+=q2.top(),q1.push(q2.top()),q2.pop();
res=(q1.size()-q2.size())*1ll*q1.top()-s1+s2;
for(register int k=;k<m;++k)MIN(f[j][k+],f[i][k]+res);
}
}
printf("%lld\n",f[n][m]);
}
return ;
}