P2034题解

题目描述

给定一行 \(n\) 个非负整数 \(a_1 \cdots a_n\)。现在你可以选择其中若干个数，但不能有超过 \(k\) 个连续的数字被选择。你的任务是使得选出的数字的和最大。

题解

正难则反，考虑将原问题转化为从 \(a\) 中选若干数使得，任意两数差不大于 \(k\),求答案最小。

观察到问题类似于滑动窗口，考虑单调队列优化dp。还是那句话如果一个选手比你小，还比你强，你就可以退役了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,k,a[N],dp[N],ans=LLONG_MAX,sum;
list<int>q;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i],sum+=a[i]; 
	memset(dp,63,sizeof(dp));
	dp[0]=0;
	q.push_back(0);
	for(int i=1;i<=n;i++)
	{
		if(q.front()<i-k-1)
		q.pop_front();
		dp[i]=min(dp[i],dp[q.front()]+a[i]);
		while(dp[i]<=dp[q.back()])
		q.pop_back();
		q.push_back(i);
	}
	for(int i=n;i>=n-k;i--)
	{
		ans=min(ans,dp[i]);
	}
	cout<<sum-ans;
	return 0;
}