方針ガチャを色々ミスってタイムロスが痛い。
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; }
まとめ
今回は実装が軽い問題が多いね。