# 最少拦截系统

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

Input

Output

Sample Input
`8 389 207 155 300 299 170 158 65`

Sample Output
`2`

n2一般dp算法：

```#include<stdio.h>
int a[30200],dp[30200];
int main() {
int n;
while(scanf("%d",&n)!=EOF) {
for(int i=0; i<n; i++) {
dp[i]=1;
scanf("%d",&a[i]);
}
int res=0;
for(int i=1; i<n; i++)
for(int j=0; j<i; j++)
if(a[i]>a[j]&&dp[i]<dp[j]+1) {
dp[i]=dp[j]+1;
if(res<dp[i])
res=dp[i];
}
printf("%d\n",res);
}
return 0;
}```

nlogn二分算法：

```#include <stdio.h>
int inf=99999999;
int n,l;
int a[30200];
int s[30200];
int find(int m) {
int la=0,lb=l;
while(lb>=la) {
int mid=(la+lb)>>1;
if(s[mid]==m)
return mid;
else if(s[mid]>m)
lb=mid-1;
else
la=mid+1;
}
return la;
}
int main() {
while(scanf("%d",&n)!=EOF) {
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
s[0]=-1;
l=1;
for(int i=1; i<=n; i++) {
s[l]=inf;
int t=find(a[i]);
if(t==l)
l++;
s[t]=a[i];
}
printf("%d\n",l-1);
}
return 0;
}
```

```#include <stdio.h>
#include <algorithm>
using namespace std;
int inf=99999999;
int a[30200],s[30200];
int main() {
int n;
while(scanf("%d", &n)!=EOF) {
for(int i=1; i<=n; i++)
scanf("%d",&a[i]),s[i]=inf;
int l=1;
for(int i=1; i<=n; i++) {
int k=lower_bound(s+1,s+n+1,a[i])-s;
if(k==l)
l++;
s[k]=a[i];
}
printf("%d\n",l-1);
}
return 0;
}```