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

深碍√TFBOYSˉ_ 2021-10-29 10:12 217阅读 0赞

#  #

*  题目大意: 给出一个序列,和\\(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<bits/stdc++.h>
    #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;
    }

写个最大字段和果然不能过QAQ  
Educational Codeforces Round 69 (Rated for Div. 2)

转载于:https://www.cnblogs.com/xxrlz/p/11229780.html