D - トランプ挿入ソート

問題

D - トランプ挿入ソート

感想

最長増加部分列むずい.....

考え方

どの要素を取り出してもよくて，それからどこに挿入してもよいということなので，取り出さなくてよい数（組）はどのようなものなのかを考えると良い。

要素を取り出して挿入するということは，その取り出した数字はsortされていなかったということになる。つまり，取り出さない数字の組は逆に言うとsort済みということである。

よって，結果的には，与えられた組に対して最長増加部分列を求めればよいことになる。

とはいえ，最長増加部分列の実装はかなり悩みました。解説ではニブタンを使ってますが自分の実装はちょっと変ですね....笑

Accepted Program

#include <iostream>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;

int main () {
  int n;
  cin >> n;
  int a[n + 1];
  map<int, int> box;
  a[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    box[a[i]] = i;
  }
  int dp[n + 2];
  for (int i = 0; i <= n + 1; i++) {
    dp[i] = 0;
  }
  int now = 0;
  for (int i = 1; i <= n; i++) {
    if (i == 1) {
      dp[i] = a[i];
      now = i;
    }  
    else {
      int jmax = a[i] - 1;
      if (a[i] > now) {
        jmax = now;  
      }
      for (int j = jmax; j >= 0; j--) {
        if (dp[j] < a[i]) {
          if (dp[j + 1] > a[i] || dp[j + 1] == 0) {
            dp[j + 1] = a[i];
            now = (j + 1 > now) ? j + 1 : now;
          }    
          break;
        }    
      } 
    }
  }
  int max = -1;
  for (int i = 1; i <= n; i++) {
    if (dp[i] > 0) {
      max = i;  
    }
  }
  cout << n - max << endl;
}