TopCoder SRM 309 Div1 Medium KMonotonic

問題

ある数列がk-monotonicであるとは、数列を連続するk個の区間に分けて、
それぞれの区間が全て単調数列（真に単調増加または単調減少）にできることを言う。

与えられた数列a[i]とkに対して、a[i]の要素を一つ選び、
その要素を+1または-1する操作を何回か繰り返して、
a[i]をk-monotonicにしたい。

このような操作は最小で何回必要か、求めよ。

制約条件

n≦50
k≦n
-20,000,000≦a[i]≦20,000,000

方針

区間[l, r]を1-monotonicにするコストを考えたい。
これは、次のようなDPにより計算できる。

dp[l][r][i]:= 区間[l, r]を、rの値をiに変更して1-monotonicにするときの最小コスト
としてこれを次の値をm通りについて更新していく。

a[i]の変更後の値として考えるべきものの候補は、{a[j] + x | jは任意、-n≦x≦n}である。

現在の値がiのとき、次の値の候補をn通り調べる必要がありそうだが、
DPを、
dp[l][r][i]:= 区間[l, r]を、rの値を"i以下"に変更して1-monotonicにするときの最小コスト
としてやればO(n^2 m)（mは値の種類）でDP出来て間に合う。

各区間を1-monotonicにするコストが求まったら、
あとはそれを使ってもう一度DPをすれば、全体をk-monotonicにするコストがわかる。

ソースコード

int n, m;
int cost[50][50], dp[50][60];

void solve(vi &s){
	static int dp[50][50][6000];
	vi v;
	rep(i, n) for(int j = -n; j <= n; j++) v.pb(s[i] + j);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	m = v.size();
	
	rep(i, n) rep(j, n) rep(k, m) dp[i][j][k] = inf;
	
	rep(i, n) for(int j = i; j < n; j++) rep(k, m){
		if(i == j) dp[i][j][k] = abs(s[i] - v[k]);
		else if(k) dp[i][j][k] = min(dp[i][j][k], dp[i][j - 1][k - 1] + abs(s[j] - v[k]));
		if(k) dp[i][j][k] = min(dp[i][j][k], dp[i][j][k - 1]);
	}
	rep(i, n) rep(j, n) rep(k, m) cost[i][j] = min(cost[i][j], dp[i][j][k]);
	
}

class KMonotonic {
	public:
	int transform(vector <int> sequence, int k) 
	{
		n = sequence.size();
		
		rep(i, n) rep(j, n) dp[i][j] = cost[i][j] = inf;
		
		rep(i, 2){
			solve(sequence);
			rep(j, n) sequence[j] *= -1;
		}
		
		static int dp[50][60];
		rep(i, n) rep(j, k + 1) dp[i][j] = inf;
		rep(i, n) for(int j = 1; j <= k; j++) rep(l, i + 1){
			dp[i][j] = min(dp[i][j], cost[0][i]);
			if(j > 1) dp[i][j] = min(dp[i][j], dp[l][j - 1] + cost[l + 1][i]);
		}
		
		return dp[n - 1][k];
	}
};