これも普段の600ptよりは簡単め。
https://atcoder.jp/contests/abc162/tasks/abc162_f
問題
N要素の整数列Aが与えられる。
ここから、floow(N/2)個の要素を選ぶ。ただし連続した要素を選んではいけない。
要素の和の最大値を求めよ。
解法
基本的には1個おきに選び、若干選び方をずらすことが許容される。
そこで以下を考える。
f(i,b,k) := i要素目までからの選び方を考えたとき、bはi要素目を選ばなかったかどうかを示し、かつkはこれまで連続で選ばなかった箇所の数を示すとき、選んだ要素の総和の最大値。
先頭は仮に手前に選ばなかった要素があるとして、f(0,true,0)=0から初めてf(i,b,k)を埋めて行く。
Nが偶数ならmax(f(N,false,1),f(N,true,0))、奇数ならmax(f(N,false,2),f(N,true,1))が解。
int N; ll A[202020]; ll dp[202020][2][3]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N+1) FOR(x,2) FOR(y,3) dp[i][x][y]=-1LL<<60; dp[0][1][0]=0; FOR(i,N) { cin>>x; FOR(j,2) FOR(k,3) { // not take if(k+j<3) dp[i+1][1][k+j]=max(dp[i+1][1][k+j],dp[i][j][k]); // take if(j==1) dp[i+1][0][k]=max(dp[i+1][0][k],dp[i][j][k]+x); } } if(N%2==0) cout<<max(dp[N][1][0],dp[N][0][1])<<endl; else cout<<max(dp[N][0][2],dp[N][1][1])<<endl; }
まとめ
こっちも500ptぐらいの印象。