Codeforces #521: Div3. F. Yet another 2D Walking

問題

N要素の整数列Aと、整数K,Xが与えられる。
AのうちX要素を選び、その総和を最大化せよ。
ただし、連続するK要素のうち、最低１個は選択されなければならない。

解法

以下のdpテーブルを考える。

• dp(n,m) := m個目まで要素を選んだ時、最後の要素がn番であるような選び方における要素の総和

dp(n+1,*)のテーブルは、dp(n,*)のテーブルをdequeに入れ、sliding windowの要領でdequeの先頭に最大値が入るようにしておけばよい。

int N,K,X;
int A[5050];

ll dp[5050][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>X;
	FOR(i,N) cin>>A[i];
	
	FOR(x,5050) FOR(y,5050) dp[x][y]=-1LL<<60;
	dp[0][0]=0;
	for(i=1;i<=X;i++) {
		deque<pair<ll,int>> D;
		D.push_back({dp[i-1][0],0});
		for(j=1;j<=N;j++) {
			while(D.size() && D.front().second<j-K) D.pop_front();
			dp[i][j]=A[j-1]+D.front().first;
			while(D.size() && D.back().first<=dp[i-1][j]) D.pop_back();
			D.push_back({dp[i-1][j],j});
		}
	}
	
	ll ret=-1;
	FOR(i,N+1) if(i>N-K) ret=max(ret,dp[X][i]);
	cout<<ret<<endl;
	
}

まとめ

ここら辺はまだ典型テクな感じ。