Codeforces #267 Div2 C. George and Job

CF#267は不参加なので練習のみ。
http://codeforces.com/contest/467/problem/C

問題

N要素の数列P[i]が与えられる。
ここから、重複しない連続したM要素の部分列をK個選ぶ。
部分列の総和を最大化せよ。

解法

まず事前に累積和を取っておき、部分列の総和はO(1)で計算できるようにしておく。
後はdp[数列内の位置][選ぶべき部分列の残り数]を状態として総和を最大化するようDPする。

• 今i番目を残りk個部分列を作るとき、
  • P[i]を右端とした部分列をとるなら、dp[i][k-1] = dp[i-M][k]+(P[i]+P[i-1]+...+P[i-M+1])
  • P[i]を右端とした部分列をとらないなら、dp[i][k] = dp[i-1][k]

int N,M,K;
ll P[5001],S[5005];
ll dp[5005][5005];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>M>>K;
	FOR(i,N) cin>>P[i];
	FOR(i,N) S[i+1]=S[i]+P[i];
	
	FOR(x,5005) FOR(y,5005) dp[x][y]=-1LL<<50;
	dp[0][K]=0;
	FOR(i,N) FOR(j,K+1) {
		dp[i+1][j]=dp[i][j];
		if(i+1>=M) dp[i+1][j]=max(dp[i+1][j],dp[i+1-M][j+1]+S[i+1]-S[i+1-M]);
	}
	cout <<dp[N][0]<<endl;
	
}

まとめ

かなり典型的なDP。