Submission #4241930

---

Source Code Expand

#include<iostream>
#include<vector>
using namespace std;

int n;
int c[3*10000];
vector<int> dp;

int dfs(int k){
  if(k == n)return 0;
  for(int i = 1; i < dp.size() ; i++){
    if(c[k] > dp[i] && i == dp.size()-1){
      dp.push_back(c[k]);
//      cout << "push " << dp[i+1] << endl;;
    }
    else if(c[k] < dp[i]){
      dp[i] = c[k];
//      cout << "change " << c[k] <<endl;
      break;
    }
  }
  dfs(k+1);
  return 0;
}

int main(){
  cin >> n;
  for(int i = 0 ; i < n ; i++){
    cin >> c[i];
  }
  dp.push_back(100000);
  dp.push_back(100000);
  dfs(0);
//  cout << dp.size() << endl;
  cout << n - dp.size()+1 << endl;
}

Submission Info

Judge Result