TopCoder SRM 627 Div2 Hard BubbleSortWithReversals

先にDiv2 Hard思いついてからDiv1 Mediumを考えてそう。
http://community.topcoder.com/stat?c=problem_statement&pm=13256

問題

N要素の数列A[i]がある。
このうち連続する要素の並び順を反転する、という処理を最大K回行える。
ただし同じ要素は２回以上反転の対象にはできない。

数列のinversionを最小化せよ。

解法

同じ要素は２回反転の対象とできないので、状態としてdp[最後に反転したindex][残り反転回数]を持ちinversion数の最小値をカウントしていけばよい。

以下の処理では、最後に反転したindexがxの状態で、A[y]～A[z]を反転した際のA[x+1]～A[z]で生じるinversion数を事前にnum[x][y][z]として計算しておき、DPを行っている。
O(N^5)なコードだけど割とループ回数は小さいので間に合う。

int num[55][55][55];
int num2[55],dp[55][55];

class BubbleSortWithReversals {
	public:
	int getMinSwaps(vector <int> A, int K) {
		int i,x,y,z,j;
		int L=A.size();
		ZERO(num);
		ZERO(num2);
		FOR(y,L) FOR(x,y) num2[y]+=A[x]>A[y];
		FOR(z,L) FOR(y,z) FOR(x,y+1) {
			for(i=x;i<y;i++) num[x][y][z]+=num2[i];
			for(i=y;i<=z;i++) {
				FOR(j,y) num[x][y][z]+=A[j]>A[i];
				for(j=i+1;j<=z;j++) num[x][y][z]+=A[i]<A[j];
			}
		}
		
		
		FOR(x,51) FOR(y,51) dp[x][y]=10000;
		dp[0][K]=0;
		int ret=10000;
		for(x=0;x<L;x++) {
			FOR(y,x) {
				dp[x][K-1]=min(dp[x][K-1],num[0][y][x]);
				FOR(i,K-1) FOR(z,y) dp[x][i]=min(dp[x][i],dp[z][i+1]+num[z+1][y][x]);
			}
			
			j=0;
			for(y=x+1;y<L;y++) j+=num2[y];
			FOR(i,K+1) ret=min(ret,j+dp[x][i]);
		}
		return ret;
	}
}

まとめ

方針はすぐ立ったけど実装に手こずった。