杭电1257

题意：对给出的序列求最少的非升序列数目。

Analyse：一开始以为用最长降序子序列来做，后来发现可以这样做：后面的数字如果比前面的所有子序列的最后一个都大，就必须要增加一个子序列（增加一个系统），否则可以添加到之前的子序列后面。

View Code

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 int a[100000];
 5 int main()
 6 {
 7     vector<int> dp;
 8     vector<int>::size_type st;
 9     int n,i;
10     while(cin>>n)
11     {
12         for(i=0;i<n;i++)
13             cin>>a[i];
14         dp.push_back(a[0]);
15         for(i=1;i<n;i++)
16         {
17             for(st=0;st<dp.size() && dp[st]<a[i];st++);
18             if(st==dp.size())
19                 dp.push_back(a[i]);
20             else
21                 dp[st]=a[i];
22         }
23         cout<<dp.size()<<endl;
24         dp.clear();
25     }
26     return 0;
27 }