线性dp——1197D

一开始没有什么头绪，后来注意到m<=10,考虑是否可以用dp[i][j]表示第i位，前面跟了j个数的最大值

那么第i+1个数，直接和第i个数的[0,m]的m+1种状态去转移即可，如果是由0或m状态拓展出去的，那么值要-k

策略和序列最大连续子段和的贪心策略一样

#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define ll long long 
#define INF 0x3f3f3f3f3f3f3f3f
ll dp[N][15],n,a[N],m,k;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[i][j]=-INF;
            
    long long ans=0;
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        dp[i+1][0]=0;
        for(int j=0;j<=m;j++)if(dp[i][j]!=-INF){
            if(j==0)
                dp[i+1][1]=max(dp[i+1][1],dp[i][j]+a[i+1]-k);
            else if(j!=m)
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+a[i+1]);
            else dp[i+1][1]=max(dp[i+1][1],dp[i][j]+a[i+1]-k);
            ans=max(ans,dp[i+1][j+1]);
            ans=max(ans,dp[i+1][1]);
        }
    }
    cout<<ans<<endl;
}