传送门
dp方程很简单啊，dp[i]=max{dp[i-r],dp[i-r+1]...dp[i-l]}+val[i];
暴力找最大值只有60分，考虑优化，很明显，用单调队列维护一个滑动窗口即可。
起点至少是l，答案的来源最多是n-l。
话说单调队列写起来好恶心啊。。。每次都写不对。。。还是要多练看来
#include<bits/stdc++.h> #define N 200005 using namespace std; int n,l,r,val[N],dp[N]; deque <int> q; int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>l>>r; for(int i=0;i<=n;i++) cin>>val[i]; for(int i=l;i<=n;i++) { while(!q.empty()&&dp[q.back()]<dp[i-l]) q.pop_back(); q.push_back(i-l); while(!q.empty()&&q.front()+r<i) q.pop_front(); dp[i]=max(dp[i],dp[q.front()]+val[i]); } int ans=0; for(int i=n-r+1;i<=n;i++) ans=max(ans,dp[i]); cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9484839.html
相关资源：各显卡算力对照表！