Submission #2177699

---

Source Code Expand

#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
#include<stack>
#include<string.h>
#include<list>
#include<limits>
#include<bitset>
#include<ctype.h>
#include<set>
using namespace std;
typedef long long int ll;
const ll MOD=10007;
const ll INF=1000000000;
const int MAX=100001;
const double EPS=1e-10;
int main(){
    int n;
    cin>>n;
    int a[1001];
    vector<int> dp(n+1,INF);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){   
        int k=upper_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        dp[k]=a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(dp[i]!=INF){
            ans=i;
        }else{
            break;
        }
    }
    cout<<n-ans-1<<endl;
    return 0;
}

                           

Submission Info

Judge Result