实测$O(nk)$能开O2过
不开O2也有90分
提交记录

代码

#include <cstring>
#include <iostream>
using namespace std;
long long int a[ 100010 ], dp[ 100010 ];
int main()
{
    int n, k;
    cin >> n >> k;
    long long int sum = 0;
    for ( int i = 1; i <= n; i++ )
    {
        cin >> a[ i ];
        sum += a[ i ];
    }
    memset( dp, 0x7f, sizeof( dp ) );
    dp[ 0 ] = 0;
    long long int ans = 0x7f7f7f7f7f7f7f7f;
    for ( int i = 1; i <= n; i++ )
    {
        for ( int j = max( 0, i - k - 1 ); j <= i - 1; j++ )
        {
            dp[ i ] = min( dp[ i ], dp[ j ] + a[ i ] );
        }
        cerr << dp[ i ] << " ";
    }
    for ( int i = n - k; i <= n; i++ )
    {
        ans = min( ans, dp[ i ] );
    }
    cout << sum - ans << endl;
}