题解 | #训练技巧#

从正面寻找最大值太难了，不如换个思维，从反面来找答案。既然题目是要求最大的训练效果，那我们就去找因为休息而浪费的最小训练效果，最后再让总的训练效果减去浪费的最小训练效果就得出答案了，这样就方便多了。要求第i天浪费的最小值，只需要找到[i-k-1,i-1]这个区间里浪费的最小值进行了。因此状态转移方程只有一种： dp[i]=1e18; for(int j=i-k-1;j<i;j++) { dp[i]=min(dp[j],dp[i]); } dp[i]+=arr[i];

#include<iostream>
using namespace std;
#define int long long
const int da=1e18;//所有的训练效果加起来最大不超过1e18
int n,k;
int sum;
int arr[100010];
int dp[100010];
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>arr[i],sum+=arr[i];
    for(int i=1;i<=n;i++)
    {
        int j=i-k-1;
        if(j<0)
            j=0;
      //j可能小于0，因此当就j<0时，使其等于0，确保数组不会越界
        dp[i]=da;
        for(;j<i;j++)
        {
            dp[i]=min(dp[j],dp[i]);
        }
        dp[i]+=arr[i];
    }
  	int ans_min =da;
    for(int i=n;i>=n-k;i--)
    {
        ans_min=min(ans_min,dp[i]);
    }
    cout<<sum-ans_min;//让总的训练效果减去休息浪费的最少训练效果
    return 0;
}