炼金术师

题目描述

爱德华以钢之炼金术师之名享誉全国，而今天他要完成弟弟阿尔冯斯提出的一个挑战。

已知爱德华和阿尔冯斯面前各摆了一块无限长的画布，画布上一开始均无任何颜色，且两块画布的最左端下标均设为ni[0,a_{i}]i$种颜色。

在阿尔冯斯使用完 次炼金术后，爱德华也会使用若干次炼金术，每次炼金术他可以选择中的任意一种颜色，以及任意的一个右端点，将该画布的区间染成此次选择的颜色。

规定后面的染色会覆盖前面的染色，比如先将区间染成第种颜色，再将区间染成第33种颜色，则此时区间的颜色是第种颜色。

请问爱德华最少要使用多少次炼金术，才能把他面前的画布变成和阿尔冯斯的画布一样。

输入描述:

第一行一个正整数，。
接下来 个正整数， 。

输出描述:

输出爱德华最少要使用多少次炼金术。

我们先分析一下样例:

输入：

3
1 2 3

输出：

1

这个样例是怎么运行的呢?

首先来看这个图：

在第一个时间点时，阿尔冯斯把1号颜色染到了这个区间上：

在第二个时间点时，阿尔冯斯把2号颜色染到了这个区间上并覆盖了的1号颜色：

在第三个时间点时，阿尔冯斯把3号颜色染到了这个区间上并覆盖了的1号颜色和的2号颜***r>

所以我们可以发现：

1. 后来的颜色是可以覆盖之前的颜色的
2. 要统计最后这条毛巾上一共有多少种颜色就可以用单调栈来维护
           1. 新加入的颜色的长度和栈顶元素比较，如果当前的这个栈顶元素的长度小于新加入的颜色的长度，就表示新加入的颜色可以覆盖栈顶元素的颜色，所以就把栈顶弹出。

        2. 遇到覆盖不了的元素就可以把这个颜色加入栈了。

代码：

#include <bits/stdc++.h>
using namespace std;
stack<int> mys;
int main()
{
    int n, x;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        while(!mys.empty() && mys.top() <= x)
        {
            mys.pop();
        }
        mys.push(x);
    }
    int ans = 0;
    while(!mys.empty())
    {
        ans++;
        mys.pop();
    }
    printf("%d\n", ans);
    return 0;
}

相信大家都看得懂吧!

都看到这儿了，就点个赞吧~

（牛币+10086001）