CS Round#53 C Histogram Partition

题意：给定一个数组A，以及一个初始值全为0的空数组B，每次可以对数组B的任意一个区间内的所有数+x，问至少几次操作能把B数组变成A数组

NOIP原题（积木大赛）升级版，话说CS怎么那么多跟NOIP原题差不多的题目，我上次还看见一道拦截导弹来着。。。

言归正传，一开始想贪心，后来发现可以构造出反例，想了一会没什么好办法就去看题解了。题解的解释非常巧妙，他将序列当作一堆矩形竖直排列在一起，最终答案就是矩形的分割数，如下：

看到这里我似乎也知道该怎么做了。我们考虑序列一开始只有一个矩形的状况，加入一个新矩形时，其对答案产生贡献当且仅当它的高度不等于第一个矩形时。可以发现这个结论可以推广到N个矩形中，如果新加入矩形的高度在相邻的不降序列中出现过，那么它将对答案产生贡献。于是维护一个单调栈即可。

#include<bits/stdc++.h>

using namespace std;

#define MAXN 200000+10

int n,top=,ans=,st[MAXN],vis[MAXN];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        int x;

        scanf("%d",&x);

        while(st[top]>x)vis[st[top--]]--;

        if(!vis[x])ans++;

        st[++top]=x;

        vis[x]++;

    }

    printf("%d\n",ans);

    return ;

}

巴特西

CS Round#53 C Histogram Partition

最新文章

热门文章