样例2,3过不去
查看原帖
样例2,3过不去
106619
yagyagyag楼主2020/6/29 14:14
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5505;
int n,w,s;
ll a[MAXN];
ll f[MAXN][MAXN];
deque<ll> dq; 
int main()
{
	memset(f,0x9f,sizeof f);
	cin>>n>>w>>s;
	for (int i=1;i<=n;i++)
		scanf("%lld",a+i);
	f[0][0]=0;
	for (int i=1;i<=n;i++){
		for (int j=min(w,i);j>=1;j--)
//			for (int k=j-1;k<=min(w,j+s-1);k++)
//				f[i][j]=max(f[i][j],f[i-1][k]+a[i]*j);
		{
			while (!dq.empty() && f[i-1][dq.back()]<=f[i-1][j]) dq.pop_back();
			dq.push_back(j);
			while (!dq.empty() && dq.front()>j+s-1) dq.pop_front();
			f[i][j]=max(f[i][j],f[i-1][dq.front()]);
			f[i][j]=max(f[i][j],f[i-1][j-1]);
			f[i][j]+=a[i]*j;
		}
	}
	ll ans=-1e18;
	for (int i=1;i<=w;i++)
		ans=max(ans,f[n][i]);
	cout<<ans<<endl;
	return 0;
}
2020/6/29 14:14
加载中...