USACO 2017 US Open Contest Gold T2: Modern Art 2

题目大意

小TY的同学HF也想创作艺术

HF只有一块长条状的画布(画条)，长度为N(所以每一次涂色只能涂上连续几个单位的颜料，同样新的颜料可以完全覆盖旧的颜料

由于他的颜料同样非常傲娇，每次涂完要等上1day才能完全干，只有旧颜料干了以后才能用新颜料覆盖

现在小HF用了2017个年头终于画出了一个大作品，自己非常满意

现在他想复制这份作品

题目分析

观察题目，可以转化成每次对一段连续区间进行染色，可以染不同的颜色，但每种颜色每次只能染一段连续区间而且每种颜色染的区间要连续而不相交，求最少染几次能染成目标状态？

若一种颜色的两端中含另外一种颜色，那么就必须先涂该种颜色，再涂那种颜色。

这就是“先进后出，后进先出”

所以，我们记录每种颜色的左右端点。

从左往右扫，若碰到一种颜色起点，则把它加进栈里。反之碰到重点，则弹出。

若碰到一种颜色不是栈顶颜色，则说明这种颜色前面涂过，中间被覆盖后又涂过，涂了两次，与题意矛盾，输出-1。

然后最大的晾干天数就是栈的最大size-1啦(因为默认先全是0，多算了一天)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=1e5+10;
 4 
 5 int n,ans;
 6 int a[MAXN];
 7 int S[MAXN],T[MAXN];
 8 int st[MAXN],top;
 9 int main(){
10     scanf("%d",&n);
11     for(int i=1;i<=n;++i){
12         scanf("%d",&a[i]);
13         if(!S[a[i]]) S[a[i]]=i;
14         T[a[i]]=i;
15     }
16     a[n+1]=0;T[0]=n+1;
17     for(int i=0,x;i<=n+1;++i){
18         x=a[i];
19         if(i==S[x]){
20             st[++top]=x;
21             ans=max(ans,top);
22         }
23         if(x!=st[top]){
24             puts("-1");
25             return 0;
26         }
27         if(i==T[x]) --top;
28     }
29     printf("%d
",ans-1);
30     return 0;
31 }