Codeforces ECR #086 : F. Make It Ascending

なんか変な上限…。
http://codeforces.com/contest/1342/problem/F

問題

N要素の整数列Aがある。
2要素を選択し、片方の値を片方に足しこんだ上、片方を削除して間を詰めるということを行う。
全体を昇順にするため必要な最小操作回数を求め、手順を答えよ。

解法

順番を無視すれば、3^N通りの列挙を行うBitDPの要領で、和がだんだん多くなるように部分集合を取っていけばよい。
この問題は順番も気にする必要があるので、
f(a,b,mask) := maskに示す要素が使用済みで、その時処理後の要素数がaで、最後にあるのはもともとb番目の要素であるような場合、処理後の最後の要素の最小値
として3^N要素総当たりするBitDPをしていけばよい。

最終的に全要素が処理済みで、かつ要素数が最も多いものを選ぼう。

int T;
int N;
int A[15];
int S[1<<15];
int from[16][16][1<<15];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		int mask;
		FOR(mask,1<<N) {
			S[mask]=0;
			FOR(i,N) if(mask&(1<<i)) S[mask]+=A[i];
		}
		FOR(i,N+1) FOR(j,N+1) FOR(mask,1<<N) from[i][j][mask]=-1;
		from[0][0][0]=0;
		int ret=0;
		FOR(i,N+1) FOR(j,N+1) FOR(mask,1<<N) if(from[i][j][mask]>=0) {
			int cur;
			int pre=from[i][j][mask]&((1<<15)-1);
			int ma=mask | j<<16 | i<<21;
			//cout<<i<<" "<<j<<" "<<mask<<endl;
			if(mask==(1<<N)-1) ret=ma;
			if(i==0) cur=0;
			else cur=S[mask]-S[pre];
			
			for(x=j;x<N;x++) if((mask&(1<<x))==0) {
				int cand=((1<<N)-1)^mask^(1<<x);
				for(int sm=cand; sm>=0; sm--) {
					sm&=cand;
					if(S[sm|(1<<x)]>cur) {
						if(from[i+1][x+1][mask^(1<<x)^sm]==-1) {
							from[i+1][x+1][mask^(1<<x)^sm]=ma;
						}
						else {
							int pre=S[mask^(1<<x)^sm]-S[from[i+1][x+1][mask^(1<<x)^sm]&((1<<15)-1)];
							if(S[sm|(1<<x)]<pre) {
								from[i+1][x+1][mask^(1<<x)^sm]=ma;
							}
						}
					}
				}
			}
		}
		vector<pair<int,int>> R;
		while(ret) {
			i=(ret>>21);
			j=((ret>>16)%32)-1;
			mask=(ret&((1<<15)-1));
			ret=from[i][j+1][mask];
			int dif=mask^(ret&((1<<15)-1));
			FOR(x,N) if(x!=j&&(dif&(1<<x))) R.push_back({x,j});
		}
		vector<int> V;
		FOR(i,N) V.push_back(i);
		cout<<R.size()<<endl;
		FORR(r,R) {
			FOR(x,V.size()) if(V[x]==r.first) break;
			FOR(y,V.size()) if(V[y]==r.second) break;
			cout<<x+1<<" "<<y+1<<endl;
			V.erase(V.begin()+x);
		}
	}
}

まとめ

復元が面倒すぎる。