yukicoder : No.258 回転寿司(2)

ループしてないのが優しさ。
http://yukicoder.me/problems/710

問題

N要素の数列V[i]がある。
これらのうちいくつかを選択し、その和が最大となるものを答えよ。
ただし隣接する要素同士をともに選択してはならない。

解法

0～i番までのうち、いくつか選択したときの合計の最大値をS[i]とする。
S[i]=max(S[i-1], S[i-2]+V[i])でSを求めて、最後にその結果をバックトラックすればよい。

以下のコードではO(N^2)で解いているが、O(N)で充分だね。

int N;
int V[1010];
int ma[2020];
int from[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>V[i];
	for(i=N-1;i>=0;i--) {
		for(x=i+2;x<N+2;x++) if(ma[i]<ma[x]+V[i]) {
			ma[i]=ma[x]+V[i];
			from[i]=x;
		}
	}
	
	int id=0;
	FOR(i,N) if(ma[i]>ma[id]) id=i;
	
	_P("%d\n",ma[id]);
	while(1) {
		_P("%d",id+1);
		id=from[id];
		if(id>=N) {
			_P("\n");
			break;
		}
		_P(" ");
	}
}

まとめ

回転寿司なんだし、最初と最後が連結しても良かったね。