链接：HDU - 4261 Estimation

题意：

给出长度为$N$N（$1\le N\le 2000$1≤N≤2000）的序列$A_1,A_2,\cdots,A_N$A1​,A2​,⋯,AN​，要求将其分为$K$K（$1\le K\le \min\{25,N\}$1≤K≤min{25,N}）段，并对每段确定一个值$B_j$Bj​（$1\le j\le K$1≤j≤K），使得$\sum|A_i-B_j|$∑∣Ai​−Bj​∣最小，其中$i$i与$j$j的关系由划分决定。

要求输出$\sum|A_i-B_j|$∑∣Ai​−Bj​∣的最小值

---

分析：

dp的方程并不难想，以处理序列当前的 前$i$i个 作为 阶段，以将前$i$i个 划分为$j$j段 作为 状态，可得：

$F(i,j)$F(i,j)表示将$A_1,A_2,\cdots,A_i$A1​,A2​,⋯,Ai​划分为$j$j段时答案的最小值；

状态转移方程：$F(i,j)=\min\limits_{0\le k\le i-1}\{F(k,j-1)+S(k+1,i)\}\;\;\;\;\;\;\;\;1\le i\le N,1\le j\le K$F(i,j)=0≤k≤i−1min​{F(k,j−1)+S(k+1,i)}1≤i≤N,1≤j≤K
其中 $S(u,v)$S(u,v)表示 将$A_u,A_{u+1},\cdots A_v$Au​,Au+1​,⋯Av​作为一段时，取合适的$B$B得到的$\displaystyle\sum_{u\le i\le v}|A_i-B|$u≤i≤v∑​∣Ai​−B∣的最小值；

初值：$F(0,0)=0$F(0,0)=0，其他均为$\infin$∞；
目标：$F(N,K)$F(N,K)

若$S(u,v)$S(u,v)可以在$O(1)$O(1)的时间复杂度内求得，则时间复杂度为$O(N^2 \cdot K)$O(N2⋅K)。

考虑预处理得到所有的$S(i,j)$S(i,j)，显然对于任意序列，要找到一个数，使得该数与序列中所有数的差值绝对值之和最小，该数必定是 序列的中位数。

动态维护一个有序序列，即可快速求得中位数，易想到利用堆来维护，但是堆并不支持随机存取，故此处要用“ 对顶堆 ”来处理。

利用一个 小根堆 来 存储当前序列中值较大的一半元素（在堆内从小到大排列），利用一个 大根堆 来存储 当前序列中值较小的一半元素（在堆内从大到小排列），这样将元素逐个与堆顶比较后加入小根堆/大根堆，并 同时对两个堆进行修正，保证其大小差值不超过1（由于“对顶堆”的大根堆和小根堆的堆顶是 “ 相连的 ”，只需将其中一个堆的堆顶元素取出并放入另一个堆即可），这样 中位数必定由小根堆和大根堆的堆顶决定。

为求得$S(i,j)$S(i,j)，每次固定$i$i，遍历$j$j，还需要维护两个堆内元素的和，从而直接求得$S(i,j)$S(i,j)，故预处理的时间复杂度为$O(N^2\log_2 N)$O(N2log2​N)。

---

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int maxn=2e3+10;
int N,K,A[maxn];
int F[maxn][30],S[maxn][maxn];
int main()
{
    while(scanf("%d %d",&N,&K)&&(N||K))
    {
        for(int i=1;i<=N;i++)
            scanf("%d",&A[i]);
        for(int i=1;i<=N;i++)
        {
            priority_queue<int,vector<int>,greater<int> > h1;   //小根堆，存较大的数
            priority_queue<int> h2;                             //大根堆，存较小的数
            int s1=0,s2=0;                                      //小根堆的和，大根堆的和
            for(int j=i;j<=N;j++)
            {
                if(h1.empty()||A[j]>=h1.top())   //若小根堆为空，或A[j]大于等于小根堆堆顶
                {                                //将A[j]加入小根堆
                    h1.push(A[j]);
                    s1+=A[j];
                }
                else                             //否则将A[j]加入大根堆
                {
                    h2.push(A[j]);
                    s2+=A[j];
                }

                //进行修正，保证小根堆大小==大根堆大小，或小根堆大小==大根堆大小+1
                while(h1.size()>h2.size()+1)
                {
                    h2.push(h1.top());
                    s2+=h1.top();
                    s1-=h1.top();
                    h1.pop();
                }
                while(h1.size()<h2.size())
                {
                    h1.push(h2.top());
                    s1+=h2.top();
                    s2-=h2.top();
                    h2.pop();
                }

                if(h1.size()==h2.size())
                    S[i][j]=s1-s2;
                else
                    S[i][j]=s1-s2-h1.top();
            }
        }
        memset(F,0x3f,sizeof(F));
        F[0][0]=0;
        for(int i=1;i<=N;i++)
            for(int j=1;j<=K;j++)
                for(int k=0;k<=i-1;k++)
                    F[i][j]=min(F[i][j],F[k][j-1]+S[k+1][i]);
        printf("%d\n",F[N][K]);
    }
    return 0;
}

• 点赞
• 收藏
• 分享
• • 文章举报

墓华 发布了213 篇原创文章 · 获赞 40 · 访问量 2万+ 私信 关注