Codeforces #700 Div1 : B2. Painting the Array II

割と手間取ってるな。
https://codeforces.com/contest/1479/problem/B2

問題

整数列Aが与えられる。
このうち一部の要素を抜き出し、元の数列中の登場順で連結したものをA0、残りをA1とする。
数列Xに対し、seg(X)とはXをRun-Length圧縮で表現したときの要素数とする。

最適なA0の選び方をしたとき、seg(A0)+seg(A1)の最小値を求めよ。

解法

dp(n,k) := Aの先頭n要素をA0,A1に分けたとき、それぞれの末尾がA[n]、A[k]であるようなときのseg(A0)+seg(A1)の最小値
とする。

nを小さい順に考えていくと、dp(n-1,*)から以下の状態遷移が行える。
dp(n,k) := dp(n-1,k)の状態に対し、A0の末尾(A[n-1])の後ろにA[n]を追加する
dp(n,n-1) := dp(n-1,k)の状態に対し、A1の末尾(A[k])の後ろにA[n]を追加し、A0とA1を逆にする

これは、区間加算と区間最小値を計算できるSegTreeを使えば、O(logN)でdp(n-1,*)からdp(n,*)を一気に埋められる。

int N;
int A[101010];
static ll const def=1<<25;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=1<<20;
		for(i=NV-1;i>=1;i--) ma[i]=min(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) {
			return ma[k];
		}
		
		ll v=val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
		return v;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N<=2) {
		cout<<1<<endl;
		return;
	}
	int ret=0;
	FOR(i,N) cin>>A[i];
	st.update(0,1,1+(A[0]!=A[1])-(1<<20));
	st.update(A[0],A[0]+1,2-(1<<20));
	for(i=2;i<N;i++) {
		// other
		int ma=min({st.getval(0,A[i])+1,st.getval(A[i],A[i]+1),st.getval(A[i]+1,N+1)+1});
		// same
		if(A[i]!=A[i-1]) {
			st.update(0,N+1,1);
		}
		y=st.getval(A[i-1],A[i-1]+1);
		if(ma<y) {
			st.update(A[i-1],A[i-1]+1,ma-y);
		}
	}
	
	cout<<st.getval(0,N+1)<<endl;
	
	
}

まとめ

本番ちょっと手間取ってるな。