题目传送门
今天介绍的这道题是UVA的1471题，也是与上一篇博客类似的滑动窗口问题。首先放出传送门
https://vjudge.net/problem/UVA-1471
题意
有一个长度为n的子序列，你的任务是删除一个连续子序列，使得剩下的序列中有一个长度最大的连续递增子序列。例如将序列{5,3,4,9,2,8,6,7,1}中的{9，2,8}，得到的序列{5,3,4,6,7,1}中就有最长的连续递增子序列{3,4,6,7}，所以长度4就是最终的答案。
分析
那么首先我们可以得到一个想法就是使用暴力法枚举删除的子序列，然后从剩下的序列中找到最长的递增子序列，这个最最原始的想法的复杂度冲上了O(n^3)，所以我们必须要对这个想法进行优化。
首先我们可以预先计算出某一个位置后面的最长连续递增子序列记作f()，然后我们可以再算出从开头到某一个位置的最长递增子序列g()，然后我们的答案就是删除序列前面的g()和后面的f()，这样我们就可以优化到O(n^2)的复杂度，看起来还不错。
我们或许可以更进一步，我们可以增加贪心与二分的思想，我们可以以删除数组为后缀的最长递增子序列做一个有序的数组，然后每次我们枚举后缀的数组的时候，就使用二分的思想去查找不大于后面的数组的数字的最大的数，这样我们就可以使整个数组加起来最大。
似乎还不错，所以所有的步骤都集中在对整个有序表的维护中了，我们这里使用set来维护，set中也可以使用lower_bound（默认有序），我们在每次插入新数字的时候，都需要对前面和后面的数字进行排除，前面如果递增子序列的长度已经比新插入数字长了，我们就可以跳过这个数字了，如果我们成功插入这个新数字了（长度有效），我们需要对后面的数字进行过滤，如果后面的数字又比这个数字大，但是子序列的长度又短，我们就可以直接删除了。这个维护的set也像滑动窗口一样，但是只不过不是只从左右两边弹出数字了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <iostream>
#include <algorithm>
#include <set>
using namespace std;
struct node{
int a,g;
node(int a,int g):a(a),g(g){}
bool operator < (const node& s) const{
return a<s.a;
}
};
set<node> s;
int main(){
int T,n;
cin>>T;
while(T--){
cin>>n;
s.clear();
int *a=new int[n+10];
int *f=new int[n+10];
int *g=new int[n+10];
g[0]=1;
for(int i=0;i<n;i++) {
cin >> a[i];
if(i){
if(a[i]>a[i-1])
g[i]=g[i-1]+1;
else
g[i]=1;
}
}
f[n-1]=1;
for(int i=n-2;i>=0;i--){
if(a[i]<a[i+1])
f[i]=f[i+1]+1;
else
f[i]=1;
}
s.insert(node(a[0],g[0]));
int ans=1;bool flag;
for(int i=1;i<n;i++){
node d(a[i],g[i]);
auto it=s.lower_bound(d);
flag=true;
if(it!=s.begin()){
--it;
ans=max(ans,it->g+f[i]);
if(it->g>=d.g)
flag=false;
}
if(flag){
s.erase(d);
s.insert(d);
it=s.find(d);
it++;
while(it!=s.end()&&it->a>d.a&&it->g<=d.g)
s.erase(it++);
}
}
cout << ans << endl;
}
return 0;
}
|