P7399 [COCI2020-2021#5] Po

· · 题解

题目 ：P7399 [COCI2020-2021#5] Po

题面

你会获得一个长度为 n 的序列 a_{i}，这个序列是由一个初始序列经过若干变换得到的。初始序列是一个长度为 n 的全0序列。可能出现的变换规则如下： 单个变换的效果为选择一个区间 [l,r]，将 a_{l},a_{l+1},\cdots a_{r} 的值加上一个正整数 x。任意两次变换的区间只能互不相交或者一个区间包含另一个区间。 你的问题是，对于给定的序列 a_i，这个序列至少是进行了多少次变换得到的。

思路

我们可以数形结合，把整个序列想象成一个二位平面，如图（此篇以第3个样例为例讲解）：

题面“变换”的意思就是把区间 [l,r] 的高度增高一个正整数层数 x （当然这个 x 可以是任意正整数，即并不需要考虑增高了多少层） 再思考一下，可以发现：任意两个部分包含的区间其实可以看做另外两个具有包含关系的区间，例如：

这里区间 [1,3] 和区间 [2,5] 的变换其实可以看作是区间 [1,5] 和区间 [2,3] 的变换，其效果是一样的。这也就是为什么题面中会有原题目中未提及的区间变换的额外规则了 （可以自己推导出来，方便理解）。

做到这里，有经验的朋友可以发现此题和P5019 铺设道路的区间修改很类似，只是有些不同。我们可以把序列看作一座座山，在山的另一边如果有与之相同的高度，就可以在一次变换中将这两边的此高度的区间变换。

例如可以把样例中的区间 [1,5] 看作一个山：

区间 [4,4] 与区间 [2,2] 的高度一样，故可以在一次变换中将这两个区间的高度变换。区间 [1,1] 与区间 [5,5] 也是如此。 样例变换过程（区间 [6,6] 在第一次也可以变换，此处变换过程是符合上述方法的过程）：

那么如何实现呢？这就可以用到单调栈了（详情请见P5788 【模板】单调栈）。

由于山的上坡是上升序列，下坡是下降序列，我们就可以把上坡中的每一个高度存在一个栈里，等到枚举到下坡的时候再一一比较，比当前高度高的栈顶元素直接弹出。如果弹到最后发现栈顶元素比当前高度小或者栈空了，就说明上坡时没有与之对应的区间可以在同一变换中变换，那么就不得不另用一次变换使当前区间变换（如果等于，就是符合要求，是可以在同一次变换中变换的）。

code:

#include<bits/stdc++.h>
using namespace std;
int n,sol,x;
stack<int>s;
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&x);
        while(!s.empty()&&s.top()>x) s.pop();//比当前高度高的直接弹出，注意要保证栈里有元素，否则可能会出错
        if(!s.empty()&&s.top()==x) continue;//符合要求直接进入下一层循环
        if(x) sol++,s.push(x);//注意，由于原序列是全0序列，所以当高度为0时是不需要变换的，也就不需要压入栈中
    }
    printf("%d",sol);
    return 0;
}

画功不好，见谅QWQ