Codeforces #165 Div1. B. Greenhouse Effect

さてB。苦戦しつつも何とか本番中に解けた。
http://codeforces.com/contest/269/problem/B

１次元の数直線上に木が並んでおり、木の種類と木の座標が与えられる。
木を並べ替えて、木の種類が１列にソートされるようにしたい。
並べ替えのために植え替える木の数を最少化する問題。

この問題では、木の座標順にソートされて木の種類が与えられる。
後の処理では木の相対的な位置だけが関係して、木の座標値は意味がないのでそちらは読み飛ばせばよい。

座標値を読み飛ばすと、整数値の並びが与えられるので、ソートのために場所を動かす値の数を最少化する問題になる。
O(N log N)でも解けるようだが、N<=5000だったので自分はO(N^2)でDPした。

左端から順にDPしていった時、今見ている数値について「右にある自分より小さな数値を左に動かす」「自分を右に動かす」のどちらが小さいかを処理していく。
また、すでにもっと左の処理で「右にある自分より小さな数値を左に動かす」処理をしていると右にある小さな数値がすでに移動済みになっているかもしれないので、すでに左に動かした数値の上限をパラメータとして持つ。
数字の位置Pと、すでに左に動かした数値Lの上限の２つのパラメータを持つのでO(N^2)。

この処理では、「自分より右にあり、自分より小さくてLより大きい」数値の数をカウントする必要がある。
これをDP処理中に行うとO(N^3)でTLEになった。

この数値は先に計算しておくとよい。
「自分より右にある数値Aの数をカウント」をO(N^2)で行い、次にそれを累積して「自分より右にあるAより大きくて自分より小さい数のカウント」をやはりO(N^2)で行うことで処理できる。

int N,M;
int T[5001];
double X[5001];
int L[5003][5003];
int NU[5003][5003];

int calc(int cur, int fin) {
	int i,j;
	if(cur>=N) return 0;
	if(L[cur][fin]!=-1) return L[cur][fin];
	
	if(fin>=T[cur]) {
		L[cur][fin]=calc(cur+1,fin);
	}
	else {
		j=0;
		//for(i=cur+1;i<N;i++) if(T[i]>=fin && T[i]<T[cur]) j++;
		j=NU[cur][fin];
		if(j>0) L[cur][fin]=min(j+calc(cur+1,T[cur]),1+calc(cur+1,fin));
		else L[cur][fin]=min(j+calc(cur+1,T[cur]),calc(cur+1,fin));
	}
	return L[cur][fin];
}

void solve() {
	int f,r,i,j,k,l;
	
	
	GET2(&N,&M);
	FOR(i,N) {
		T[i]=GETi();
		scanf("%lf",&X[i]);
	}
	
	MINUS(L);
	
	FOR(i,N) for(j=i+1;j<N;j++) if(T[i]>T[j]) NU[i][T[j]]++;
	FOR(i,N) for(j=T[i]-1;j>=0;j--) NU[i][j]+=NU[i][j+1];
	int res=calc(0,0);
	
	_P("%d\n",res);
	return;
}

まとめ

O(N^3)の回答までは割とすぐ到達。
その後「Lより大きくて自分より小さい」数値の数のカウントに迷ったが、うまくかけて良かった。