Codeforces #371 Div1 C. Sonya and Problem Wihtout a Legend

ギリギリで気づいたけど実装が間に合わなかった。
http://codeforces.com/contest/713/problem/C

問題

N要素の数列A[i]が与えられる。
この数列を、狭義単調増加な数列にしたい。

1要素を1増減させるのにかかるコストを1とする。
条件を満たすのに必要な最小のコストを求めよ。

解法

狭義単調増加という条件が扱いにくいので、A'[i]=A[i]-iで数列を変換しよう。
あとはA'[i]を広義単調増加する問題と置き換えることができる。

だとすると、各要素を増減させるとして、増減させた先の値はA'[i]のいずれかにさせればよく、その他の値であえて留める理由はない。
そうすると各A'[i]をどの値に移動させるか、状態はO(N^2)通り。
各状態について、コストの総和の最小値を答えればよい。

int N;
ll A[3030];
int cand[3030];
ll dp[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]-=i;
		cand[i]=A[i];
	}
	sort(cand,cand+N);
	FOR(i,N) dp[0][i]=abs(A[0]-cand[i]);
	
	for(i=1;i<N;i++) FOR(x,N) {
		dp[i][x] = dp[i-1][x] + abs(cand[x]-A[i]);
		if(x) dp[i][x] = min(dp[i][x], dp[i][x-1] - abs(cand[x-1]-A[i]) + abs(cand[x]-A[i]));
	}
	cout<<*min_element(dp[N-1],dp[N-1]+N)<<endl;
	
}

まとめ

ここ２回CFが不調だ。