TopCoder SRM 779 : Div1 Easy Div2 Hard ArraySorting

解法は難しくないけど、Easyの割に面倒。
https://community.topcoder.com/stat?c=problem_statement&pm=15960&rd=17848

問題

整数列Aが与えられる。
これらのいくつかの要素を任意の整数に変え、全体を単調増加にしたい。
変更する要素数が最小のもののうち、得られるAで辞書順最小のものを求めよ。

解法

辞書順最小ということは、先頭からどん欲に決めていきたいわけだが、その際は以降の処理における変更回数を事前に求めておきたい。
そこで、後ろから順に以下を求めておこう。
f(i,k) := (変更後の)A[i]以降のsuffixにおいてA[i]=kであるもののうち変更数最小値
とすると
f(i,k) = (A[i]==k) + min(f(i+1,m)) (mはk以上)
となる。
あとはf(i,k)をすべて埋めたら先頭からどん欲に変更数最小値のうち一番小さなkを適宜選んでいけばよい。

int dp[2020][2020];
int nex[2020][2020];

class ArraySorting {
	public:
	vector <int> arraySort(vector <int> A) {
		reverse(ALL(A));
		A.push_back(0);
		reverse(ALL(A));
		int N=A.size();
		int x,y;
		for(x=1;x<=2000;x++) dp[N-1][x]=(A[N-1]!=x);
		
		for(x=N-2;x>=0;x--) {
			int mi=202020,ne=202020;
			for(y=2000;y>=(x?1:0);y--) {
				
				if(y && dp[x+1][y]<=mi) {
					mi=dp[x+1][y];
					ne=y;
				}
				dp[x][y]=mi+(A[x]!=y);
				nex[x][y]=ne;
			}
		}
		vector<int> R;
		int cur=0;
		FOR(x,N-1) {
			cur=nex[x][cur];
			R.push_back(cur);
		}
		return R;
		
	}
}

まとめ

復元パートが面倒。