Codeforces #260 Div1 A. Boredom

CF260に参加。なんとかABCを解いてレート自己ベスト更新。
http://codeforces.com/contest/455/problem/A

問題

整数配列A[i]がある。

ここで数A[i]を選択すると、A[i]ポイント得られる代わりに、A[i]及びにA中でA[i]-1・A[i]+1の値を持つものをすべて削除する。
Aが空になるまで最適手を取る場合、最大何ポイント得られるか。

解法

A[i]を選択しても、同じ数字のものは消えないので、消す数字xを選択するとA中xの個数×xだけポイントを得られる。

A中の各数字xの数をカウントしてC[x]とすると、後は数字を小さい順にDPしていけばよい。
x-1を選択している場合、xは選択できないので、xまでの数字を使った場合の最大ポイントをP[x]とするとP[x]=max(P[x-1],P[x-2]+x*C[x])でDPできる。

int N,A[100005];
ll dp[100005];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A[x]++;
	}
	dp[1]=A[1];
	for(i=2;i<=100002;i++) {
		dp[i]=max(dp[i-1],dp[i-2]+A[i]*(ll)i);
	}
	cout << dp[100002] << endl;
	
	
}

まとめ

このあたりはすんなり。