UVa 11572 Unique Snowflakes——思路题

UVa 11572 Unique Snowflakes——思路题

这个题划分一下子问题就很好理解了

设ans【i】是以第i个元素为首的最长集合的长度，

那么求解过程便是对于每一个i，尽量将其无限延长，直到出现重复元素为止，那么结果便是所有ans【i】的最大值

实际操起来时，我们可以用【L, R）表示一个序列的区间，开始L = R = 0，然后将R无限延长直到出现重复元素，这时直接将L + 1，然后继续无限延长R，出现重复元素后再把L + 1......过程中及时更新最优解ans，最后输出ans即可

判断是否重复用set容器即可

#include #include #include #include #include using namespace std;const int maxn = 1000000 + 10;int a[maxn];int main(){ int T, n; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); set s; int L = 0, R = 0, ans = 0; while (R < n) { while (R < n && s.count(a[R]) == 0) s.insert(a[R++]); ans = max(ans, R - L); s.erase(a[L++]); } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。