ABC134 E - Sequence Decomposing

E - Sequence Decomposing

こういう問題、どこをとっかかりにして考えれば良いのかがまだ掴めていないのが弱いなあと。

問題文

N個の整数からなる数列Aが与えられます。
N個それぞれの整数に対して、色を1つ選んでその色を塗ります。 この時、以下の条件を満たす必要があります:

A_iとA_j (i < j) が同じ色で塗られているならばA_i < A_j が成立する
条件を満たすように色を塗る時、用いる色の数の最小値を求めてください。

概要

まあ同じ色が塗られている数列を部分列とした時に、出来るだけ小さい単調増加部分列に分割しろという問題です。

単調増加部分列と言えば「最長増加部分列」問題が有名です。DPやセグ木やBITを使った解法がたくさんあります。
しかしここでは最長増加部分列を求めるだけでは不足で、部分列群を求める必要があります。

で、まあここで僕は思考が止まってしまうんですが......。
一番単純なのは、
「実際に適切な単調増加部分列群を構築していくことが出来ないか？」→「出来ますね」→「出来ました」
というステップを踏むことでしょう。

解法

ある単調増加部分列群が既に存在しているとして、前から数列を見ていきます。そして最も適切な部分列の末尾に新しい数を追加していくことで、最小の単調増加部分列群が求められます。
ここで適切な部分列を複数ある部分列群からどう決定するかですが、末尾の数と新しい数の差が最も小さい部分列に追加すれば良いです。

例えば末尾の数が1の部分列に10を加えるよりも、末尾が9の部分列に10を加えた方が損が少なくなります。
10の次に3が来た時、前者の場合だと部分列群の構成が [{1,10}, {9}] となり、新たに3を末尾に持つ部分列を加えて [{1,10}, {9}, {3}] となってしまいますが、後者の場合だと[{1, 3}, {9}] となり、こちらの方が望ましいです。

部分列群の末尾だけ見れば良いことが以上より分かるので、multisetで末尾の数だけ管理します。
既存の部分列の末尾に新しく数を追加する場合は、それまでの末尾の数を削除して新しい数を代わりに入れます。新たな部分列を作成せざるを得ない場合は、ただ新しい数を入れれば良いです。

よって実装は以下になります。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

int main(int argc, char const *argv[]) {
	int n;cin>>n;
	multiset<ll> mst;
	rep(i,n) {
		ll x;cin>>x;
		auto itr = mst.lower_bound(x);
		if (mst.begin()!=itr) --itr, mst.erase(itr);
		mst.insert(x);
	}
	cout << mst.size() << endl;
	return 0;
}