Estimation

给出一个长度为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
\]

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

枚举左端点i，设大根堆为H，小根堆为E
初始化\(m(i,i)=0,k=-a_i\)，H加入\(a_i\)
枚举右端点j
如果\(a_j\leq H.top()\)，那么\(E.push(H.top()),H.pop(),k+=E.top()\times 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()\times 2\)
计入答案\(m(i,j)=k+(2q-p)\times 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\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;

}

巴特西

Estimation

解

最新文章

热门文章