yukicoder : No.324 落ちてた閉路グラフ

恥ずかしながら、誘導部分グラフって言い回し初めて聞いた。
http://yukicoder.me/problems/879

問題

N頂点N辺からなる輪を成すグラフがある。
i番の辺のスコアは順にW[i]である。

このN頂点からM頂点を選び誘導部分グラフを作成したい。
誘導部分グラフの辺の総スコアの最大値を求めよ。

解法

こういう円形状になっているもののDPの定番ネタとして、DPを始めた点の状態を覚えつつ順にDPしていこう。

dp[最初の点の選択の有無][直前の点の選択の有無][頂点番号][選択済み頂点数] := そのような状態を満たす最大スコア
として状態を管理し、最初の頂点を選択した場合、しない場合それぞれについてDPをすれば良い。

int N,M;
int W[5000];
int dp[3][3][3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>W[i];
	
	memset(dp,0xce,sizeof(dp));
	
	dp[0][0][0][0]=dp[1][1][0][1]=0;
	int ma=-100000000;
	FOR(r,2) {
		FOR(i,N-1) {
			FOR(j,M+1) {
				dp[r][0][i+1][j]=max(dp[r][0][i][j],dp[r][1][i][j]);
				if(j) dp[r][1][i+1][j]=max(dp[r][0][i][j-1],dp[r][1][i][j-1]+W[i]);
			}
		}
		
		ma=max(ma,dp[r][0][N-1][M]);
		if(r==0) ma=max(ma,dp[r][1][N-1][M]);
		if(r==1) ma=max(ma,dp[r][1][N-1][M]+W[N-1]);
	}
	
	
	cout<<ma<<endl;
	
}

まとめ

すごそうな閉路グラフが落ちていたというが、（グラフが落ちてる…は置いておいて）ずいぶん平易な形状ではないかい？