最少拦截系统的个数等于最长上升子序列的长度。别问我为什么，我不知道。这是个结论，之前看到过。
用O(nlogn)的最长上升子序列算法即可。
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int n;
while(cin>>n)
{
int x,ans(0);
vector<int> d(n+1,-1);
for(int i=1;i<=n;i++)
{
cin>>x;
if(x>d[ans])
d[++ans]=x;
else
{
vector<int>::iterator p=upper_bound(d.begin(),d.begin()+ans+1,x);
*p=x;
}
}
cout<<ans<<endl;
}
return 0;
}
posted on 2011-03-07 18:13
lee1r 阅读(558)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划