【题解】JZOJ6636 / 洛谷P3668 [USACO17OPEN] Modern Art 2 G

link

题意

有一条长度为 n n n 的画布。初始时全部为 0 0 0。每次染色可以将一个区间染成同一种颜色,每种颜色只能染一次。每次操作可以染色若干次,但是染色的区间两两不相交。颜色可覆盖。问最少操作多少次能够使画布变成 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,,an。若无法做到则输出 -1

题解

发现对于最外面的颜色肯定是最早涂的,颜色会构成一个包含关系。区间有交叉则不合法。可以拿一个栈存储颜色,如果遍历到这个颜色第一次出现的位置,那么将这个元素压入栈中。遍历到颜色的结尾,就弹出元素。

容易发现,栈大小的最大值就是答案。因为每种颜色只能涂一次,所以每种颜色一定是涂出现位置的最左边和最右边之间。那么栈里面的元素都可以理解为还没有涂的颜色。这些颜色是满足包含关系的,也就是说不能同时涂。

考虑无解的情况。对于每个 a i a_i ai,若其不是这种颜色的第一次出现的位置,且栈顶的元素与其不同,就可以判定为无解。这说明在颜色 a i a_i ai 的应涂区间中出现了别的颜色,同时这个颜色与 a i a_i ai 不构成包含关系。也就是说,无论先涂两种颜色中的哪一种,都会有颜色被覆盖掉,无法变成目标状态。

时间复杂度 O ( n ) O(n) O(n)

代码

短得一匹。文章来源地址:https://www.uudwc.com/A/Y6PvJ/

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N], s[N], e[N], ans = 0, st[N], tp = 0;//s[i] 表示颜色 i 最早出现的位置,e[i] 表示颜色 i 最晚出现的位置
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s[a[i]] = !s[a[i]] ? i : s[a[i]], e[a[i]] = i;
	s[0] = 0, e[0] = n + 1;
	for (int i = 0; i <= n + 1; i++) {
		if (s[a[i]] == i) st[++tp] = a[i], ans = max(ans, tp);
		if (a[i] != st[tp]) { printf("-1"); return 0; }
		if (e[a[i]] == i) tp--;
	}
	printf("%d", ans - 1);
	return 0;
}

原文地址:https://blog.csdn.net/inferior_hjx/article/details/132818504

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

上一篇2023年09月12日 04:44
Opencv cv2.putText 函数详解
下一篇 2023年09月12日 04:45