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;
} 题解 文章被收录于专栏
竞赛养老选手佛系刷题~
查看28道真题和解析