「USACO17OPEN」Modern Art 2

题意：

现在给你一个长度为 $N(N\le 10 ^5)$ 的画条。上面有若干种颜色，每位的数字表示一种颜色，$0$ 表示没有涂色。为了快捷，每次涂色可以用一种颜色填充一个区间，同一种颜色只能使用一次。每次可以涂色好几次，但是这些区间必须分别连续切两两不能相交。然后等待 1day 油漆干了后再同样操作，输出创作完成并全干了后的最少时间。

一道括号序列的变形问题。

记录每一种颜色的起始点以及终点，可以想象，如果染色次数要最少，那么最外一层的颜色要最先涂。

于是我们维护一个栈，把每个颜色加入栈，最大染色次数就是栈最大的元素个数。

对于每一种颜色 $a[i]$，如果起始位置就在 $i$，说明要多涂一次，入栈，更新答案；如果是终止位置就退栈。

如果 $a[i]$ 与栈顶颜色不同，则无解(因为此时正在涂另一种颜色，由于一种颜色只能涂一次，肯定无解)。

$0$ 不填颜色，所以出栈位置为 $n+1$，先让 $0$ 入栈，并且最后出栈，但是不能计入答案，所以最后答案减 $1$。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],ans;
int s[maxn],t[maxn];
int stack[maxn],top;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(!s[a[i]])
			s[a[i]]=i;
		t[a[i]]=i;
	}
	t[0]=n+1;
	for(int i=0;i<=n;i++)
	{
		int p=a[i];
		if(i==s[p])
		{
			stack[++top]=p;
			ans=max(ans,top);
		}
		if(p!=stack[top])
		{
			printf("-1");
			return 0;
		}
		if(i==t[p])
			top--;
	}
	printf("%d",ans-1);
	return 0;
}
//类似括号序列，同一种颜色只能涂一次！！！
//用个栈维护一下，如果开始新颜色就入栈，如果结束就出栈，如果在中间，且颜色与栈顶不同肯定无解。