Modern Art 2
提交数: 5, 通过率: 100%, 平均分: 100
题目描述:
Having become bored with standard 2-dimensional artwork (and also frustrated at others copying her w
ork), the great bovine artist Picowso has decided to switch to a more minimalist, 1-dimensional styl
e.Although, her paintings can now be described by a 1-dimensional array of colors of length N(1≤N≤
100,000), her painting style remains unchanged: she starts with a blank canvas and layers upon it a
sequence of "rectangles" of paint, which in this 1-dimensional case are simply intervals. Sheuses ea
ch of the colors 1…Nexactly once, although just as before, some colors might end up being completel
y covered up by the end.To Picowso's great dismay, her competitor Moonet seems to have figured out h
ow to copy even these 1-dimensional paintings, using a similar strategy to the preceding problem: Mo
onet will paint a set ofdisjoint intervals, wait for them to dry, then paint another set of disjoint
intervals, and so on.Moonet can only paint at most one interval of each color over the entire proce
ss. Please compute thenumber of such rounds needed for Moonet to copy a given 1-dimensional Picowso
painting.
伟大的牛艺术家皮科沃已经厌倦了标准的二维艺术作品，也在伤心其他人复制她的作品，她决定转向更简约，一维
的风格。尽管如此,她的作品现在可以表示描述颜色的一维数组长度N(1≤N≤100000)，她的绘画风格没有改变:她
以一个空白的画布开始，一次涂色只能涂上连续几个单位的颜料，同样新的颜料可以完全覆盖旧的颜料，每次涂完
要等上1day才能完全干，只有旧颜料干了以后才能用新颜料覆盖。皮科沃十分沮丧的是，她的对手Moonet似乎已经
找到了如何复制这些一维的绘画，使用类似的策略。前面的问题：Moonet会画几组不相交区间，等待他们干，然后
画几组不相交区间，等等。Moonet同一种颜色只能使用一次。请计算该轮Moonet复制一个给定的一维picowso绘画
所需要的时间。
输入格式:
The first line of input contains N, and the next N lines contain an integer in the range 0…N
indicating the color of each cell in the 1-dimensional painting (0 for a blank cell).
第一行为N，画条长度
从第2行至N行每行一个数表示要涂颜色
输出格式:
Please output the minimum number of rounds needed to copy this painting, or -1 if this could not hav
e possibly been an authentic work of Picowso (i.e., if she could not have painted it using a layered
sequence of intervals, one of each color).
输出一个整数表示最少天数。数据若不合法则输出-1
样例输入:
7 0 1 4 5 1 3 3
样例输出:
2
提示:
In this example, the interval of color 1 must be painted in an earlier round than the intervals of c
olors 4 and 5, so at least two rounds are needed.
空间限制: 128MB
来源: Usaco2017 Open Gold