Codeforces #327 Div1 D. Top Secret Task

ちょっと手間取ったけど、何とか本番解けた。
http://codeforces.com/contest/590/problem/D

問題

N要素の整数列Qがある。
隣接２要素の交換を最大S回まで行えるとき、先頭K要素の総和の最小値を求めよ。

解法

Qの後ろから先頭K要素に入れるか入れないか判定していく。
入れない場合、後ろに前半K個に入れる要素があるとき、その数だけ交換が必要となる。

dp[処理している位置][前半K個に入れる要素数][総交換数] := (前半K個に入れる要素の最小値)
としてDPしていく。O(N^4)でもなんとか間に合う。

int N,K,S;
int Q[1010];

int from[151][150*161],to[151][150*161];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,N) cin>>Q[i];
	
	FOR(x,N) FOR(y,150*80) from[x][y]=1<<29;
	from[0][0]=0;
	for(i=N-1;i>=0;i--) {
		for(x=K;x>=0;x--) for(y=150*80;y>=0;y--) {
			to[x][y]=1<<29;
			if(from[x][y]<1<<29) {
				// take
				if(x<K) to[x+1][y] = min(to[x+1][y],from[x][y]+Q[i]);
				// nottake
				to[x][y+x] = min(to[x][y+x],from[x][y]);
			}
		}
		swap(from,to);
	}
	
	int mi=1<<29;
	FOR(i,min(S+1,N*(N-1)/2+1)) mi=min(mi,from[K][i]);
	cout<<mi<<endl;
	
}

まとめ

問題文ややこしすぎないですかね…。