kmjp's blog

競技プログラミング参加記です

AtCoder ABC #162 : F - Select Half

これも普段の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ぐらいの印象。