典型子序列问题
在比赛中很多时候暴力枚举的方法往往是一种没有办法需要考虑全部情况时，才迫不得已使用的办法，我们往往可以把大问题转化为许多子问题进行求解，来降低时间上的消耗。
在做这种问题时我们最基本的思路就是先观察数据的范围，需要对数据的范围有一定的敏感度，如1e5我们可以想到或许是归并，二分，子问题，贪心，维护队列……这种方面去思考问题，如1e7左右的数据我们又可以想到这是否是一种找规律，DP……在此，本文列出一些较典型的题目供大家参考，希望能提供一些启发。
在本文开始之前我们先列出规模的上限，这只能说是一个大概的理想型，我们可以通过对cache的改善，程序的优化让时间复杂度尽量往这方面靠近。
| 运算量 | n！ | 2n | n3 | n2 | nlog2n | n |
|---|---|---|---|---|---|---|
| 最大规模 | 11 | 26 | 464 | 10000 | 4.5*1e6 | 100000000 |
| 速度扩大两倍后 | 11 | 27 | 584 | 14142 | 8.6*1e6 | 200000000 |
一：最大连续和（在区间内求一段连续区间的最大值）。
解法：1.DP（如果前序为负数则舍去） 2.二分(代码如下)
1 int maxsum(int left,int right)
2 {
3 if(right-left==1) return max(a[left],a[right]);
4 if(right==left) return a[left];
5 int L,R,mid;
6 mid=(left+right)/2;
7 int maxs=max(maxsum(left,mid-1),maxsum(mid+1,right));
8 L=a[mid-1],R=a[mid+1];
9 int temp=0;
10 for(int p1=mid-1;p1>=left;p1--) L=max(L,temp+=a[p1]);
11 temp=0;
12 for(int p2=mid+1;p2<=right;p2++) R=max(R,temp+=a[p2]);
13 return max(maxs,L+R+a[mid]);
14 }二：选择不相交区间（数轴上有n个开区间，选择尽量多的区间，使其没有公共点）
解法：贪心：只需考虑右节点的大小进行排序即可。
1 for(int i=1;i<=n;i++)
2 if(a[i].sta>=point){
3 point=a[i].last;
4 ans++;
5 }三：区间选点问题（数轴上有n个闭区间，选择尽量少的点，使每个区间至少有一个点）
解法：贪心：既然要最少那么我们可以把点直接选到每个区间的最后位子上。
1 for(int i=1;i<=n;i++)
2 {
3 // cout<<a[i].sta<<" "<<a[i].last<<'\n';
4 if(a[i].sta>point){
5 point=a[i].last;
6 ans++;
7 }
8 }四：区间覆盖问题（数轴上有n个闭区间，选择尽量少的区间覆盖一条指定线段[s,t]）
解法：贪心：首先舍去非此区间的线段，然后进行排序，进行递归化操作
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,sta,last,ans=0;
4 struct node{
5 int a,b;
6 bool operator <(const node&x)const{return a<x.a||(a==x.a&&b>x.b);}
7 };
8 vector<node> v;
9 int main()
10 {
11 scanf("%d%d%d",&n,&sta,&last);
12 while(n--)
13 {
14 node tmp; scanf("%d%d",&tmp.a,&tmp.b);
15 if(tmp.a<sta||tmp.b>last) continue;
16 v.push_back(tmp);
17 }
18 sort(v.begin(),v.end());
19 for(int i=0;i<v.size();i++)
20 if(sta!=v[i].a) continue;
21 else last==v[i].b?printf("%d",++ans):sta=v[i].b;
22 return 0;
23 }五：Gergovia的酒交易（uva11054）
解法：扫描法（将数据从左到右进行扫描，产生一些重要的量进行计算），从左到右进行排查，往右进行状态转移。
1 while(scanf("%d",&n)!=EOF&&n)
2 {
3 long long int ans=0,a,last=0;
4 for(int i=1;i<=n;i++)
5 {
6 scanf("%lld",&a);
7 ans+=abs(last);
8 last+=a;
9 }
10 printf("%lld\n",ans);
11 }六：唯一的雪花（uva 11572）
找一段最长的子序列让其中每个数都不相同
解法：合理利用链表或用STL进行求解，此处列出链表的做法。
1 #include<cstdio>
2 #include<map>
3 using namespace std;
4 const int maxn =1e6+10;
5 int a[maxn],last[maxn];
6 map<int,int> cur;
7 int main()
8 {
9 int T,n; scanf("%d",&T);
10 while(T--)
11 {
12 scanf("%d",&n); cur.clear();
13 for(int i=0;i<n;i++)
14 {
15 scanf("%d",&a[i]);
16 if(!cur.count(a[i])) last[i]=-1;
17 else last[i]=cur[a[i]];
18 cur[a[i]]=i;
19 }
20 int L=0,R=0,ans=0;
21 while(R<n){
22 while(R<n&&last[R]<L) R++;
23 ans=max(ans,R-L);
24 L++;
25 }
26 printf("%d\n",ans);
27 }
28 return 0;
29 }七：滑动窗口的最小值问题（数组中求长度为1到n-k+1的长度为k的子序列中最小值）
解法：基础的滑动窗口，建议用STL的deque解决此问题。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,k;
4 const int maxn = 1e4+10;
5 struct node{
6 int val,num;
7 }a[maxn];
8 deque<node> que;
9 vector<int> ans;
10 int main()
11 {
12 scanf("%d%d",&n,&k);
13 for(int i=1;i<=n;i++)
14 {
15 scanf("%d",&a[i].val); a[i].num=i;
16 while(!que.empty()&&que.front().num<=i-k) que.pop_front();
17 while(!que.empty()&&a[i].val<que.back().val) que.pop_back();
18 que.push_back(a[i]);
19 if(i>=k) ans.push_back(que.front().val);
20 }
21 for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
22 return 0;
23 } 八：防线（详见LIS博客中的第二题）
九：平均值（在一段01串中寻找一个长度至少为L的连续子列，使其平均值最大）
解法：有点创新的数形结合，维护动态队列的做法，通过画图可发现是一个维护凸点的动态队列题目，详情可去查询CSDN中的一些较为详细的题解，此处只列出核心代码部分。
1 for(int i=L;i<=n;i++)
2 {
3 int s=i-L;
4 while(front<rear&&k(q[rear],s)<=k(q[rear-1],q[rear])) rear--;
5 q[++rear]=s;
6 while(front<rear&&k(q[front],i)<=k(q[front+1],i)) front++;
7 double m=k(q[front],i); int l=i-q[front]+1;
8 if(m==ans&&l<len||(m>ans))
9 {
10 ans=m; len=l;
11 start=q[front]; end=i;
12 }
13 }十：不无聊的序列（uva1608）
在一个任意的连续子序列中至少有一个只出现一次的元素，则为不无聊的队列。
解法：这道题好想的一点是二分进行查找一个序列中的单独出现的元素，但是搜索的方式还是独特的，从正反两个方向搜索去减少极端情况的出现加上链表的双向存储去完成O（1）判断。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 1e5 + 10;
4 int n,a[maxn];
5 int bef[maxn],last[maxn];
6 map<int,int> m;
7 bool judge(int L,int R)
8 {
9 if(L>=R) return true;
10 int len=(R-L)/2+1,p; bool f=false;
11 for(int i=0;i<len;i++)
12 {
13 int p1=L+i,p2=R-i;
14 if((bef[p1]<L||bef[p1]==0)&&(last[p1]>R||last[p1]==0))
15 {f=true; p=p1; break;}
16 if((bef[p2]<L||bef[p2]==0)&&(last[p2]>R||last[p2]==0))
17 {f=true; p=p2; break;}
18 }
19 return f?judge(L,p-1)&&judge(p+1,R):false;
20 }
21 int main()
22 {
23 memset(bef,0,sizeof(bef));
24 memset(last,0,sizeof(last));
25 scanf("%d",&n);
26 for(int i=1;i<=n;i++)
27 {
28 scanf("%d",&a[i]);
29 if(!m.count(a[i])) bef[i]=0;
30 else {bef[i]=m[a[i]]; last[m[a[i]]]=i;}
31 m[a[i]]=i;
32 }
33 if(judge(1,n)) printf("Non_boring.");
34 else printf("Boring.");
35 return 0;
36 }以上是一些比较典型的例题，大部分都是在数组中进行操作，以大化小，在判断的时候进行舍去，避免做不必要的无用功来达到比较合理的时间消耗，希望以上的题目可以有所启发。
