「POJ 3666」Making the Grade 题解（两种做法）

0前言

感谢yxy童鞋的dp及暴力做法！

1 算法标签

优先队列、dp动态规划+滚动数组优化

2 题目难度

提高/提高+

CF rating：2300

3 题面

「POJ 3666」Making the Grade 路面修整

4 分析题面

4.1 简要描述

给出数列 A, 求非严格单调不上升或单调不下降, 且S=∑Ni=1|Ai−Bi| 最小的序列B，输出S

4.2 模型转换

输入N, 然后输入N个数，求最小的改动这些数使之成非严格递增或非严格递减即可

5 问题分析

以B为非严格单调递增为例

5.0 暴力

我们直接当考虑已经选了n个数：

• 若n=1，A1=B1时S最小为|A1−B1|

• 若n>1，前面已经选择了n-1个数，取得了最小值，考虑怎么取第n个数

  • 若 Ai≥Bi−1，Bi=Ai显然最优

  • 若Ai<Bi−1

    • Bi=Ai

    • 将Bk,BK+1,...,Bi都赋值为Ak,Ak+1,...,Ai的中位数

    口胡证明：
    

    我们可以将Bk,BK+1,...,Bi标记在数轴上
    

    再将Ak,Ak+1,...,Ai标记上
    

    那么，其实S的几何含义就是每一组Ai到Bi的距离之和
    

    我们的小学数学也学过绝对值最值问题：
    

    求|x−k1|+|x−k2|+|x−k3|...的最小值
    

    其实和这里的S是没有任何区别的
    

    所以，我们知道零点分段法可以解决这类问题
    

    就是取中位数（就是使每个绝对值内部为0的x答案数组的中位数）
    

    可以使得绝对值之和最小
    

    

  1. 如果x在两个k之间,那么无论x在哪,距离之和都是这两个k的距离

  2. 如果在这两个k之外,那么距离之和则为两个k距离加上两倍的x距近的k的距离，肯定不会优于于第一种情况

     那么我们只要尽量让x在越多的k之间即可

     那么最佳解x在图中就是4,如果k的个数为偶数n,则是kn/2和Kn/2+1之间

     综上，选择中位数最佳

5.1 法一 dp（动态规划）

通过综上分析(5.0中)，我们直接暴力模拟肯定是不行的（这个复杂度直接爆掉了）

但是！

我们可以从中得到一个very important的结论：

B数列中的每个数必定都为A数列中的元素

所以，我们可以考虑用dp来解决：

阶段：到第i位

状态：dpi,j表示以Bj结尾的Smin

B数组是A的复制排序处理过后的数组

   dp[i][j]表示把前i个数变成不严格单调递增且第i个数变成原来第j大的数的最小代价

转移方程：dpi,j=min(dpi−1,k)+|Ai−Bj|,其中1≤j≤n,1≤k≤j

5.2 法二 堆（优先队列）

5.2.1 内心思考

现在我们可以重新想一下，既然是需要求非严格单调递增，那么重要的是什么呢？

当前序列的最大值。（这一点应该是肯定的）

最大值？

是不是有什么奇怪的想法了？

...

堆！

所以就简单搞个大根堆吧！

5.2.2 模拟过程

begin...

      数据 ：1 3 2 4 5 3 9

i=1:

      堆：空，a[i]=1，top=空

这个时候堆是空的，肯定要放进去

      ∴把a[i]放入堆中

      ->堆：1 ，a[i]=1，top=1

i=2:

      堆：1 ，a[i]=3，top=1

这个时候a[i]>top，就是说明满足非严格单调递增

      ∴把a[i]放入堆中

      ->堆：3 1 ，a[i]=3，top=3

i=3:

      堆：3 1 ，a[i]=2，top=3

这个时候a[i]

最节省的方法肯定花费top-a[i]来进行更改

更改后会得到(a[i],a[i]),(a[i]+1,a[i]+1)....(top-1,top-1),(top,top)这些二元组

这里面肯定是有合法的二元组，肯定也是有不合法的

再引入一个变量：newtop:当前top被pop掉过后的top

我们可以肯定，在上面所有的二元组当中，是有可以满足值≥newtop的，所以这对二元组是一定可以满足非严格单调递增，那么后面的数据也只需要满足数值≥newtop就可以了

所以我们就需要使得这对二元组的数值尽量不对后面的操作产生影响，那么就放入两个最小值，即a[i]。

      ∴把top给pop掉，a[i]和a[i]放入堆中

      ->堆：2 2 1 ，a[i]=2，top=2

这个时候放入两个a[i]是合法的，那么我们就来看一种放入两个a[i]不合法的情况

...

i=6

      堆：5 4 2 2 1 ，a[i]=3，top=5

按照我们之前讨论的操作进行过后，会是

      堆：4 3 3 2 2 1 ，a[i]=3，top=4

      原序列: 1 2 2 4 3 3

这个时候我们可以发现如果是把a[5]改成3，在原序列看上去是不合法的，但是这问题大吗？

不大。

因为我们更改过后的二元组不一定非是3 3，它也可以是4 4，5 5，那么这样就是合法的了，我们把3丢进去的原因就是为了尽量不影响后面的操作，让后面要是进行变化也会变得尽量小，更好维护非严格单调递增

5.2.3 总结

也就是说，我们需要明确，堆里面存的可能不是最终的序列，它里面存的就是当前序列需要满足的最小值。

6 实现细节

6.1 法一：dp（动态规划）

6.1.1 滚动数组

从我们的dp方程：dpi,j=min(dpi−1,k)+|Ai−Bj|,其中1≤j≤n,1≤k≤j

灰常容易地阔以算出空间复杂度是O(n2)

这个。。秉承着我们能省则省的原则

看到这个开二维数组O(n2)的空间貌似有点浪费

那怎么去优化空间呢？

又由于我们的dp方程中只用到了i−1的信息

于是我们下意识地反应：

——用滚动数组优化！

  用位运算符&来记录，这样就只用了0/1来表示

重复利用，节省空间

     i&1的效果和i%2的效果是一样的，但是i&1要快一点

     且这种方式比直接写0/1少了一个不断交换的过程

     窝jio得这个东西还是很·····香的

将i−>i & 1，i−1−>(i−1)&1

方程就变成了这样：

dp[i&1][j]=min(dp[(i−1)&][k])+|A[i]−B[j]|,其中1≤j≤n,1≤k≤j

6.1.2 最小值

但是这个复杂度。。

看上去好像是3层循环，就是O(n3)啊

在n<=2000 的时候就已经game over了，显然不行啊

这个xiao问题应该有手就行吧

其实只要一边更新min(f[i−1][k])一般算当前的f[i][j]就行

（因为k只到j）

6.1.3 降序

不严格单调不上升的情况也一样

更加方便的是可以把B数组从大到小排序后，做单调不下降的dp就🆗了

6.1.4 时间复杂度

二维DP，所以就是O(n2)

6.2 法二 堆（优先队列）

6.2.1 具体操作

以非严格单调递增为例

搞一个大根堆，依次遍历数组

• 当堆为空的时候直接push

• 当a[i]≥top的时候直接push

• 当a[i]<top的时候，ans+=top-a[i]，先pop再push两次a[i]（一个用来代替原pop，一个是本身）

那非严格单调递减就是相反的了

最后把两种的ans去一个min就好了

6.2.2 时间复杂度

堆的一堆操作，所以就是O(nlogn)

7 代码实现

7.1 法一：dp（动态规划）

#include
using namespace std;
const int N=2e4+2;
int n,f[2][N],a[N],b[N],ans=0x3f3f3f3f;
bool cmp1(int x,int y){
    return x//升序 
bool cmp2(int x,int y){
    return x>y;
}//降序 
void work(){
    for(int i=1;i<=n;i++){
        f[1][i]=abs(a[1]-b[i]);
    }//边界条件
    for(int i=2;i<=n;i++){
        int minn=f[(i-1)&1][1];
        for(int j=1;j<=n;j++){
            minn=min(minn,f[(i-1)&1][j]);//边更新边求
            f[i&1][j]=minn+abs(a[i]-b[j]);
            //滚动数组 
        }
    } 
    for(int i=1;i<=n;i++){
        ans=min(ans,f[n&1][i]);
    }//求答案
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];//拷贝到b数组
    }
    sort(b+1,b+1+n,cmp1);//从小到大 
    work(); //dp计算
    sort(b+1,b+1+n,cmp2);//从大到小 
    work();//直接就是一样的啊

    printf("%d",ans);//输出最小
    return 0;
}

7.2 法二：堆（优先队列）

#include
using namespace std;
int n;
int a[3100];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);//读入
    priority_queue<int>q;//大根堆，处理非严格单调递增
    int ans=0,sum=0;
    for(int i=1;i<=n;i++){
        if(q.empty())q.push(a[i]);//空
        else{
            if(q.top()<=a[i])q.push(a[i]);//如上解释操作
            else{
                ans+=abs(a[i]-q.top());//加上答案
                q.pop();//弹出
                q.push(a[i]);//放入两次
                q.push(a[i]);
            }
        }
    }
    priority_queue<int,vector<int>,greater<int> >p;//小根堆，处理非严格单调递减
    for(int i=1;i<=n;i++){
        if(p.empty())p.push(a[i]);//空
        else{
            if(p.top()>=a[i])p.push(a[i]);//如上解释
            else{
                sum+=abs(a[i]-p.top());//加上答案
                p.pop();//弹出
                p.push(a[i]);//放入两次
                p.push(a[i]);
            }
        }
    }
    printf("%d",min(ans,sum));
    return 0;
}

十分简单清晰明了

8 总结

1. 最大的收获：就算做不出来也需要想一些可能的做法，说不定就撞对了

2. 新鲜的知识：更优秀的滚动数组写法|堆的奇妙用法

3. 相似的题目：CF #371 div.1 C Sonya and Problem Wihtout a Legend