Educational Codeforces Round 69 D [dp]

题意

给出长度为n的序列a，与两个整数m,k,选择一个子数组，令最大。

题解

设dp数组 代表前i个数字中，选择第个数字作为子数组中第的数字时的最大值。
很容易得到转移方程
当时
其他情况

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
using namespace std;

const ll maxn = 3e5 + 10;
const ll mod = 1e9 + 7;

ll dp[maxn][15];
ll a[maxn];


int main()
{   
    ll n,m,k;
    cin>>n>>m>>k;
    for(ll i = 1;i <= n;++i)cin>>a[i];
    ll res = 0;
    for(ll i = 1;i <= n;++i){
        for(ll j = 0;j < min(i,m);++j){
            if(j == 0) dp[i][j] = max(a[i] - k,dp[i-1][m-1] + a[i] - k);
            else dp[i][j] = dp[i-1][j-1]+a[i];
            res = max(res,dp[i][j]);
        }
    }
    cout<<res<<endl;
   return 0;
}