codeforces 1197D-Yet Another Subarray Problem

怼烎@ 2023-06-05 12:44 41阅读 0赞

传送门：[QAQQAQ][]

题意：给你一个序列，求一个子序列a\[l\]~a\[r\]使得该子序列的sum(l,r)-k\*(r-l+1+m+1)/m值是在所有子序列中最大的，并输出最大值

思路：比赛的时候使用O(n)写的，但是被hack了，因为O(n)无法记录当前距离下一次-k还有多少，若用单调队列维护也不知道前面应该弹出多少（可能现在把前面弹出是最优的，但是到后面可能因为个数还没到m的倍数，把前面加进去又是最优的），所以我们考虑再加一维

法一：dp\[i\]\[j\]表示序列到i截止，这一轮已经进行了j次取数（j=(len+m-1)%m），那么dp\[i\]\[j\]维护的就是起点为s=i-j+1-m\*t(t>=0)这个集合的最优，这样所有的dp\[i\]\[j\]就可以维护以i截止的最优答案了

对于当前i更新有两种情况：第一种是只取当前这个a\[i\]这个在dp\[i\]\[1\]特判即可

第二种是还要取前面的，dp\[i\]\[j\]从dp\[i-1\]\[j-1\]（因为dp\[i-1\]\[j-1\]所维护的s集合和dp\[i\]\[j\]所维护的s集合是一样的）转移即可（注意边界条件）

（之前HCY玄学又加了一层循环更新，一直看不懂，后来发现他虽然答案是对的，但m次更新中只有1次是有效的）

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const ll inf=200000000000000;
     
    int n,m;
    ll ans=0,dp[300005][20],sum[300005],a[300005],k;
     
    int main()
    {
        scanf("%d%d%lld",&n,&m,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++) dp[i][j]=-inf;
        }
        dp[1][1]=a[1]-k; 
        for(int i=2;i<=n;i++)
        {
            dp[i][1]=a[i]-k;
            for(int j=1;j<=min(i,m);j++)
            {
                if(j==1) dp[i][j]=max(dp[i][j],dp[i-1][m]+a[i]-k);
                else dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i]); 
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) ans=max(ans,dp[i][j]);
        }
        cout<<ans<<endl;
        return 0;
    }//

法二：

和比赛时我的思路很像，只不过这里多加了一层维护start\_point%m=rnd，进行m次尺取法即可（在时间够的情况下，搞不清楚当前单调队列弹出几个是最优的，那么就枚举，这样就不用担心前面要弹出什么了，只需在len%m=0时判断是否要把起始点重置即可）

即如果当前的和减去k\*t小于0，那么就重新开始，否则继续加

注意ans在每一次向后扩展时都要更新

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=300005;
    ll ans=0,n,a[N],m,k;
     
    int main()
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int rnd=1;rnd<=m;rnd++)
        {
            ll len=0; ll now=0;
            for(int i=rnd;i<=n;i++)
            {
                if(len%m==0) if(now-len/m*k<0) now=0,len=0;
                now+=a[i]; len++;
                ans=max(ans,now-(len+m-1)/m*k);
            }
        }
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11241525.html

[QAQQAQ]: https://codeforces.com/contest/1197/problem/D