思路

前缀和&单调队列优化DP
状态定义
f[i][0]:表示以i结尾且该数字不选所得到的最大效率值
f[i][1]:表示以i结尾且该数字选择所得到的最大效率值
转移方程
f[i][1]=max(f[j][0]+s[i]-s[j]), 其中i-k<=j<=i即从上个不选的坐标开始到i之前
f[i][0]=max(f[i-1][0], f[i-1][1])
合并状态方程可以得到
f[i][1]=max(f[j][0]-s[j])+s[i]
将f[j][0]-s[j]看做关于坐标j的整体, 可以进行单调队列优化DP求解

c++

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=1e5+5;  
LL s[N], f[N][2];
deque<int> q;
int n, k;

int main(){
    memset(f, 0x00, sizeof f);
    memset(s, 0x00, sizeof s);
    cin>>n>>k;
    q.clear();
    q.push_back(0);
    for(int i=1; i<=n; ++i){
        cin>>s[i];
        s[i]+=s[i-1];
    }

    // 单调队列优化DP
    for(int i=1; i<=n; ++i){
        f[i][0]=max(f[i-1][0], f[i-1][1]);
        while(!q.empty() && q.front()<i-k) q.pop_front();
        f[i][1]=f[q.front()][0]-s[q.front()]+s[i];
        while(!q.empty() && f[i][0]-s[i]>f[q.back()][0]-s[q.back()]) q.pop_back();
        q.push_back(i);
    }
    cout<<max(f[n][0], f[n][1])<<endl;
}