ループしてないのが優しさ。
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(" "); } }
まとめ
回転寿司なんだし、最初と最後が連結しても良かったね。