做这道题的时候，看到n=1000，还有20组的样例数量，以为必须n^2呢，但是这题其实不然，其实居然是一道剪枝的题目，在本题中通过n^2枚举两个区间的端点，然后计算往外扩散的长度大小，这个地方要o（n）实现，通过尺取就可以了，相当于这个选了重复的，就要退栈直到把另外一个给删掉为止好加入下一个，然后枚举其中一个区间的长度，通过用空间换时间的办法，o（1）找到在另外一个区间可以取到的最大位置即可。然后在这次循环不能更新答案的时候退出，剪枝减少复杂度即可。
我感觉我这么剪没有有效降低复杂度啊，不知道就过了，可能数据比较水吧（后来看了数据，真的是数据比较水啊）。
#include<iostream> #include<cstring> #include <string> #include<algorithm> #include<map> #include<set> #include<stack> #include<queue> #include <math.h> #include<vector> #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long ll; const int maxn=1e5+20; const int mod=1e9+7; typedef unsigned long long ull; typedef long long ll; int a[maxn],h[maxn]; set<int> S,S1; int main() { int T,num=1; cin>>T; while(T--) { int n; scanf("%d",&n); // cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); // cin>>a[i]; } int ans=1; S.clear(); S1.clear(); for(int i=n,len1=0;i>0;i--) { while(i-len1>0&&S.count(a[i-len1])==0) { S.insert(a[i-len1]); h[a[i-len1]]=i-len1; len1++; } for(int j=1,len2=0;j<i;j++) { while(j+len2<i&&S1.count(a[j+len2])==0) { S1.insert(a[j+len2]); len2++; } int t=len1; for(int k=j;k<j+len2;k++) { if(t+len2<=ans)//剪枝，没有过不了 break; if(S.count(a[k])) { t=min(t,i-h[a[k]]); } ans=max(ans,t+k-j+1); } len2--; S1.erase(a[j]); } len1--; S.erase(a[i]); } printf("Case #%d: %d\n",num,ans); // cout<<"Case #"<<num<<": "<<ans<<endl; num++; } }
2016 EC final C. Mr. Panda and Strips. n^3尺取+剪枝
原文：https://www.cnblogs.com/King-of-Dark/p/11644115.html