4 条题解

  • -1
    @ 2026-10-21 9:32:57

    先写一个暴力dp,写完就能发现可以单调队列优化(是个长度为m的滑动窗口)

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int n,m,a[100007],f[100007][2],l=1,r=1;
    pair<int,int> qu[100007];
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n;++i){
            cin>>a[i];
            a[i]+=a[i-1];
        }
        f[1][0]=a[1];
        qu[1]={1,a[1]};
        for(int i=2;i<=m;++i){
            f[i][1]=a[i];
            f[i][0]=a[i-1];
            while(l<=r&&qu[r].second>=a[i]-a[i-1]){
                --r;
            }
            qu[++r]={i,a[i]-a[i-1]};
        }
        for(int i=m+1;i<=n;++i){
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            f[i][1]=max(f[i][1],a[i]-qu[l].second);
            while(l<=r&&qu[l].first<=i-m){
                ++l;
            }
            while(l<=r&&qu[r].second>=a[i]-f[i][0]){
                --r;
            }
            qu[++r]={i,a[i]-f[i][0]};
        }
        cout<<max(f[n][0],f[n][1]);
        return 0;
    }
    

    信息

    ID
    329
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    135
    已通过
    23
    上传者