hdu----(1257)最少拦截系统（dp/LIS）

 1 //#define LOCAL
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<iostream>
 6 using namespace std;
 7 const int inf=0x3f3f3f3f;
 8 int n;
 9 vector<int>aa,ans;
10 int binary(int v,int len)
11 {
12   int r=len,l=1,mid;
13   while(l<=r)
14   {
15        mid=l+(r-l)/2;
16        if(ans[mid]<=v)
17       l=mid+1;
18     else
19       r=mid-1;
20   }
21   return l;
22 }
23 
24 int LIS()
25 {
26   int i,res=1,j;
27   for(i=1;i<=n;i++)
28     ans[i]=inf;
29   for(i=1;i<=n;i++)
30   {
31       j=binary(aa[i],res);
32       if(res<j) res=j;
33       if(ans[j]>=aa[i])
34         ans[j]=aa[i];
35   }
36   return res;
37 }
38 int main()
39 {
40     #ifdef LOCAL
41     freopen("test.in","r",stdin);
42     #endif
43   while(scanf("%d",&n)!=EOF)
44   {
45       aa.resize(n+2);
46       ans.resize(n+2);
47       for(int i=1;i<=n;i++)
48         cin>>aa[i];
49    printf("%d\n",LIS());
50   }
51  return 0;
52 }