AtCoder ABC #134 : E - Sequence Decomposing

方針ガチャを色々ミスってタイムロスが痛い。
https://atcoder.jp/contests/abc134/tasks/abc134_e

問題

N要素の数列が与えられる。
各要素を何色かで塗り分けたい。
ただし、同色の要素は、添え字が小さいものほど値が小さくなるようにしたい。

最少何色で塗り分けられるか。

解法

要はできるだけ少ないLISに分割できればよい。
数列の先頭から順に、既存のLISの末尾に追加できるか検討しよう。

今見ている値をvとする。
後のことを考えると、末尾はできるだけ小さく保っておいた方がいいので、追加するなら追加すべきLISは、末尾がv未満の物のうち最大のところである。
もしv未満のものが無ければ、しょうがないので新規にvを先頭とするLISを作る。

上記処理では実際にはLISの値を全部覚えておく必要はないので、末尾の値だけmultisetにでも入れておこう。

int N;
int A[101010];

int V[101010];
int num[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	multiset<int> M;
	FOR(i,N) {
		cin>>x;
		auto it=M.lower_bound(x);
		if(it!=M.begin()) M.erase(--it);
		M.insert(x);
	}
	cout<<M.size()<<endl;
	
}

まとめ

今回は実装が軽い問題が多いね。