Educational Codeforces Round 69 (Rated for Div. 2) D

#

题目大意: 给出一个序列,和\(m,k\),求\(\sum_{i=l}^{r}{a_i}-k\left \lceil \frac{r-l+1}{m} \right \rceil\)最小(可以选择空数组)
思路: 由于m最大只有10,我们可以枚举每个长度为\(1 到m-1\)的区间(\(\left \lceil \frac{r-l+1}{m} \right \rceil=1\)).
\(dp[i]\)代表从\(1到i\)的最大值,先求出\(i到i-m+1\)子数组的最大值,然后直接减去\(k\),在用\(dp[i-m]\)来更新当前的\(dp[i]\)

\[dp[i] = max(dp[i],dp[i-m]+sum[i]-sum[i-m]-k);\]

因为\(dp[i-m]\)代表的是前面以\(i-m\)结尾的子数组的最大值,而且转移应携带整个\(m\)长的区间(保证取的子数组连续)

include
define ll long long
define FOR(i,n) for(int i =1; i <= n;++i )
define FOR0(i,n) for(int i =0; i < n;++i )
define inf 0x3f3f3f3f
using namespace std;

const int maxn = 3e5+10;
ll n,k,m;
ll a[maxn];
ll sum[maxn];
ll dp[maxn];
int main(){
    cin >> n >> m>> k;
    FOR(i,n){
        cin >> a[i];
        sum[i] = sum[i-1] + a[i] ;
    }
    ll ans = 0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m&&j<=i;++j){    // 枚举 1 到 m 的区间
            dp[i] = max(dp[i],sum[i]-sum[i-j]);
        }
        dp[i] -= k;
        dp[i] = max(dp[i],0LL);
        if(i>m){                        // 前一个 来更新当前的
            dp[i] = max(dp[i],dp[i-m]+sum[i]-sum[i-m]-k);
        }
        ans = max(ans,dp[i]);
    }
    cout << ans <<endl;
    return 0;
}