题解 CF1197D 【Yet Another Subarray Problem】

· · 题解

这题的突破口在如何利用好m\le10上。

可以想到，我们如果单纯地用前缀和暴力枚举，复杂度是n^2的。

那么我们想一下，如果m=1，该怎么做呢？

很明显，只要前面的sum>0就加上（sum+=a[i]），否则新开一档（sum=a[i]），复杂度为n，同时，每一格都要减去k。

如果m=2呢？我们把情况分成两种，一种是我选取区间的右端点i满足i\%2=1，还有一种则是i\%2=0。

为什么要这么分？因为我们需要进行分块，我们单独处理这两种情况。第一种情况下我们把分块的区间列出来[1,1][2,3][4,5]...，第二种则是[1,2][3,4][5,6]...，我们可以发现，因为第一种的区间右端点满足i%2=1，左端点j，假设右端点在第id_i块分块，左端点在id_j块分块，那么我们答案需要的代价就是(id_i-id_j+1)\times k，也就是说，右端点与左端点之间（包括左右）的总块数就是文中说的向上取整的答案也就是[\frac{r-l+1}{m}]\times k。

那么我们均摊一下，给每个块的值都整体减去k，处理出分块的里面的值的总和sum_i和最大值maxn_i和分块的最大后缀值r_i。

转移就是maxn_i=max(maxn_{i-1}+sum_i,r_i)。

因为对于m=2的情况有两种分块方式，所以我们需要做两次，但是每次的复杂度都是O(n)，总体就是O(2\times n)。

那么对于10\ge m的所有情况来说，我们同样只是有了m种分块方式而已，那么最大复杂度O(10\times n)

代码：

#include <bits/stdc++.h>
using namespace std;

int n,k,m;
long long a[300005];
long long sum[300005];
long long r[300005];
long long ans;
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int f=1;f<=m;f++)
    {
        long long maxn=0;
        for(int i=f;i>=1;i--)
        {
            sum[1]+=a[i];
            r[1]=max(sum[1],r[1]);

        }
        r[1]-=k;
        sum[1]-=k;
        for(int K=1;K<=(n-f)/m;K++)
        {
            for(int i=K*m+f;i>(K-1)*m+f;i--)
            {
                sum[K+1]+=a[i];
                r[K+1]=max(sum[K+1],r[K+1]);
            }
            sum[K+1]-=k;
            r[K+1]-=k;
        }
        for(int i=1;i<=(n-f)/m+1;i++)
        {
            maxn=max(maxn+sum[i],r[i]);
            ans=max(maxn,ans);
            sum[i]=0;
            r[i]=0;
        }
    }
    printf("%lld\n",ans);
}