UVA-1471 Defense Lines 扫描+二分

题目链接:https://vjudge.net/problem/UVA-1471

题意

给出一个序列,要求删除一子序列以后,能够得到一个最长的连续递增子序列,输出这个连续递增子序列的长度

题解

前期处理

我们可以将问题分成两个部分:求以j开头的最长递增子序列的长度g[j];求以i结尾的最长递增子序列的长度f[i],这样的话问题就转化成了求i和j满足条件:A[i]< A[j] 并且 f[i]+g[j] 最大

二分查找

我们还可以在上面的O(n^2)算法的基础上继续改进,首先我们开一个数组Min,其中元素Min[i]表示长度为i的递增序列中的结尾元素值最小的值。
可见Min一定是递增的,因为长度为的n的最后一个元素的值一定比长度为n-1的序列的最后一个元素值大。这样的话我们已知A[i]的值就可以通过二分查找(lower_bound)来判断其在Min中的位置,从而得出能够取到的最长的序列长度。这样二分查找的时间复杂度为O(logn),这个算法的时间复杂度为O(nlogn)。

代码

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
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=200005;
int t,n,a[maxn],Left[maxn],Right[maxn],Min[maxn];
// 初始化确定左右两边的值
void init()
{
scanf("%d",&n);
Left[0]=1;
Right[n-1]=1;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(i)
{
Left[i]=1;
if(a[i]>a[i-1]) Left[i]+=Left[i-1];
}
}
for(int i=n-2;i>=0;i--)
{
Right[i]=1;
if(a[i]<a[i+1]) Right[i]+=Right[i+1];
}
}
int fun()
{
int ans=0;
memset(Min,INF,sizeof(Min));
for(int i=0;i<n;i++)
{
int len=lower_bound(Min+1,Min+1+n,a[i])-Min; //根据元素值得到最小延伸值
ans=max(ans,Right[i]+len-1);
Min[Left[i]]=min(Min[Left[i]],a[i]); //更新延伸值对应的元素值
}
return ans;
}
void solve()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
printf("%d\n",fun());
}
}
int main()
{
freopen("input.txt","r",stdin);
solve();
return 0;
}