最少攔截系統(tǒng)的個數(shù)等于最長上升子序列的長度。別問我為什么，我不知道。這是個結(jié)論，之前看到過。
用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 閱讀(569)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃