题解 P5019 【铺设道路】

_yjk · 2019-08-15 15:35:41 · 题解

题目链接

我的博客

众所周知，这道题和积木大赛是同一道题

题意就是给出一段自然数序列，每次操作(L,R)把区间[L,R]的数全部减一，不允许出现负数，问把序列变为零的最小操作次数

贪心做法

样例

6   
4 3 2 5 3 5 

大概长这个样子

我们考虑第一列的四块格子，最少需要4次操作给消除掉

在考虑第二列的3个格子时，发现都可以在第一列的4次操作中一起消除掉

第三列的格子也都可以一起消除掉

考虑第四列，我们可以发现，第四列下面的两个格子在前面的操作中可以一起消除，但是上面的三个是至少再进行三次操作才能消除的

而第五列下面的两个格子在第一列的操作中可以消除，上面的一个格子可以在第四列的操作中删除

考虑第六列，上面的2个格子是前面操作消除不了的，需要2次操作

那么答案就是4+3+2=9

这样大概可以总结出做法：当a_{i-1}<a_i时，ans+= a_i - a_{i-1}

贪心证明

下面用差分序列给出这个贪心的证明：

我们对原序列\{a_i\}维护一个差分数组\{diff_i\}

原序列不妨在最后加一个0，

6   
4 3 2 5 3 5 0

差分数组是

4 -1 -1 3 -2 2 -5

每次操作可以表示为diff[L]--,diff[R+1]++

最终的状态就是差分数组全部变成0

首先，每次操作最多让一个大于零的diff_i -1，所以 最优解ans>=sum(diff_i,diff_i>0)

下面要证明 ans=sum(diff_i,diff_i>0)

我们只要每次操作能让一个大于0的diff_i -1,同时后面一个小于0的diff_i +1才能够使ans=sum(diff_i,diff_i>0)

然而有一个限制条件：a_L~a_R之间没有零 否则这个操作就是不合法的

我们可以利用以下性质构造解法：

性质1：由题意知任意时刻a_i>=0，若diff_i>0 则a_i>a_{i-1}>=0,得a_i>0

性质2：由于a_{n+1}=sum(diff_i)=0,对于一个大于零的diff_i,sum(diff_{1}~diff_{i})=a_i>0,它的后面一定存在小于零的diff_i

于是有：每次选一个大于零的diff_i作为操作的左端点L,它右边的第一个小于零的diff_j作为R+1，已知a_L>0,[L,R]中任意diff_k>=0,可得任意a_k属于[L,R],a_k>=a_{k-1}>=a_L>0,因此该操作合法

所以存在至少一种操作方法可以在sum(diff_i,diff_i>0)次操作后使得diff序列全部为0，ans=sum(diff_i,diff_i>0)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN=100010;

int n,ans;

int main()
{
    scanf("%d",&n);
    int x,last=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        if(x>last) ans+=x-last;
        last=x;
    }
    printf("%d\n",ans);
    return 0;
}