[luoguP3668] [USACO17OPEN]Modern Art 2 现代艺术2（栈）

传送门

还是一个字——栈

然后加一大堆特判

至少我是这么做的

我的代码

#include <cstdio> #include <iostream> #define N 100001 #define max(x, y) ((x) > (y) ? (x) : (y)) int s[N], a[N], b[N]; int n, top, ans; inline int read() int main() for(i = 1; i <= n; i++) if(s[top] == a[i] && b[a[i]] > 1) else if(s[top] == a[i] && b[a[i]] == 1) else if(b[a[i]] == 1) ans = max(ans, top + 1); else } if(top) puts("1"); else printf("%d\n", ans); return 0; }

　　

看了题解

发现预处理出来每种颜色最左边和最右边的位置会更好处理

如果两种颜色有交集，直接输出1

题解代码

#include<bits/stdc++.h> using namespace std; typedef long long LL; int n; int a[100008],l[100008],r[100008]; int s[100008],top; int tmp,ans; int main() for(int i=1;i<=n;i++) else continue; } if(l[a[i]]==i) s[++top]=a[i]; tmp++; ans=max(ans,tmp); } if(r[a[i]]==i) } cout<<ans; return 0; }

　　

5

1 2 1 2 1

这组数据，我输出1，题解输出2

好像题解错了，但因为数据水，所以，你懂的

上一篇：hihoCoder#1196 : 高斯消元&#183;二（开关灯问题）

下一篇：[BZOJ1572] [Usaco2009 Open]工作安排Job（贪心 + 堆）

---

栈