AtCoder Beginner Contest 006D

D - トランプ挿入ソート

操作をまとめる

同じカードを選ぶ意味は無いので，各カードに対して高々1回としてよい．

(1枚抜く) -> (1枚入れる) -> (1枚抜く) -> (1枚入れる) -> ...

の操作列だが順序を入れ替えて，カードをまとめて抜く，まとめて入れるとしてよい．

操作が複数ある問題の場合，入れ替えてシンプルにできるケースがあるので，操作の順を入れ替えたときにどうなるかは考える価値がある．

LIS

カードをまとめて抜くとする．

・残ったカード全体が増加列になることが必要．また，十分であることも容易．

・抜くカードの枚数が最小になることは，残ったカードの枚数が最大になることと同値．

したがって，LIS に帰着できた．

typedef long long ll;

using vll = vector<long long>;  using vvll = vector<vll>;

#define srep(i,s,t) for (ll i = (s); i < (t); ++i)

#define rep(i,n) srep(i,0,(n))

int main() {

    ll n, m, k, q;

    cin >> n;

    vll a(n); rep(i,n) { cin >> a[i]; }

    vll dp(n+1, INFL);

    rep(i,n){

        auto it = lower_bound(all(dp), a[i]);

        *it = a[i];

    }

    auto it = lower_bound(all(dp), INFL);

    cout << n - (it - dp.begin()) << endl;

    return 0;

}