给出一个长度为n序列\(\{a_i\}\)，将其划分成连续的K段，对于其中一段\([l,r]\)，设其中位数为m，定义其权值为\(\sum_{i=l}^r|m-a_i|\)，求最小的权值之和,\(n\leq 2000,K\leq 25\)。

解

显然设\(f[i][j]\)表示前i个数划分成j段的的最小权值和，设\(m(i,j)\)为\(i\sim j\)的作为一段的权值，所以有

\[f[i][j]=\min_{0\leq k<i}\{f[k][j-1]+m(k+1,i)\}\]

边界：\(f[0][0]=0\)，其余无限大

答案：\(f[n][K]\)

注意到时间复杂度\(2000^2\times 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\]

于是对于权值，我们只要维护这样一个式子即可，步骤如下

1. 枚举左端点i，设大根堆为H，小根堆为E
2. 初始化\(m(i,i)=0,k=-a_i\)，H加入\(a_i\)
3. 枚举右端点j
4. 如果\(a_j\leq H.top()\)，那么\(E.push(H.top()),H.pop(),k+=E.top()\times 2,H.push(a_j),k-=a_j\)
5. 否则\(E.push(a_j),k+=a_j\)
6. 如果\(i-j+1\)为偶数的话，那么\(H.push(E.top()),E.pop(),k-=H.top()\times 2\)
7. 计入答案\(m(i,j)=k+(2q-p)\times H.top()\)

参考代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define il inline#define ri register#define intmax 0x7fffffffusing namespace std;int a[2001],m[2001][2001],dp[2001][26];priority_queue
         
          
           ,less
           
             >H;priority_queue
            
             
              ,greater
              
                >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
               
                dp[k][j-1]+m[k+1][i]) dp[i][j]=dp[k][j-1]+m[k+1][i]; printf("%d\n",dp[n][K]); } return 0;}il void read(int &x){ x&=0;ri char c;while(c=getchar(),c==' '||c=='\n'||c=='\r'); 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;}