D. Yet Another Subarray Problem （DP | | 枚举起点） Educational Codeforces Round 69 (Rated for Div. 2)

链接：https://codeforces.com/contest/1197/problem/D

题意：给定一个长度为 n 的数组，选择一段 [ l , r ] [l,r] [l,r] ，使得公式 ∑ i = l r a [ i ] − k ⌈ r − l + 1 m ⌉ \sum_{i=l}^r a[i] -k\lceil \frac{r-l+1}{m} \rceil ∑i=lr​a[i]−k⌈mr−l+1​⌉的值最大

思路：

• 方法1：枚举选择的起点 i ，在区间的第一个元素减去 k 。在区间的最后一个元素统计一下最小值。只在 (j -i)%m==m-1 的时候，统计最小值，这可以保证起点永远是 i + a m i + am i+am 。统计最小值的目的是用 sum - mi 更新答案（即取前缀和）。如果你在每一个位置都更新了最小值，相当于每次都更新了起点，那么你在固定点减去 k 就是错误的。前一段减去的是 k，后半段减去的是 2k

• 方法2：设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示当前为第 i 位，区间长度%m为 j 的最大值

  转移方程：

  d p [ i ] [ j ] = { m a x ( d p [ i − 1 ] [ j − 1 ] + a [ i ] − k , a [ i ] − k )   j = 0 d p [ i − 1 ] [ j − 1 ] + a [ i ]   j ! = 0 dp[i][j]=\begin{cases} max(dp[i-1][j-1]+a[i]-k,a[i]-k) \ j=0\\ dp[i-1][j-1]+a[i] \ j!=0 \end{cases} dp[i][j]={max(dp[i−1][j−1]+a[i]−k,a[i]−k) j=0dp[i−1][j−1]+a[i] j!=0​

• 方法3：其实可以看到，m 个数字是一个段，每一个数字都可以由前 m 个字符更新过来。设 d p [ i ] dp[i] dp[i]表示当前位置为 i i i 的最大值 d p [ i ] = m a x { d p [ j ] + p r e f [ i ] − p r e f [ j ] − k , i − m ≤ j ≤ i − 1 } dp[i]=max\{dp[j]+pref[i]-pref[j]-k ,i-m\le j \le i-1\} dp[i]=max{dp[j]+pref[i]−pref[j]−k,i−m≤j≤i−1}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+10,mod=1e9+7;
int n,m,k;
int a[maxn];

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i) cin>>a[i];
    ll ans=0;
    for(int i=0;i<m;++i)
    {
        ll sum=0,mi=0;
        for(int j=i;j<=n;++j)
        {
            sum+=a[j];
            if((j-i)%m==0)
                sum-=k;
            ans=max(ans,sum-mi);
            if((j-i)%m==m-1)
                mi=min(sum,mi);
        }
    }
    cout<<ans<<"\n";
    return 0;
}
           

其实也可以不取最小值，把小于0的sum直接舍弃，重新累积，也是同样等价的写法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+10,mod=1e9+7;

int n,m,k;
int a[maxn];

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i) cin>>a[i];

    ll ans=0;
    for(int i=1;i<=m;++i)
    {
        ll sum=0,mi=0;
        for(int j=i;j<=n;++j)
        {
            sum+=a[j];
            if((j-i)%m==0)
                sum-=k;
            ans=max(ans,sum);
            if((j-i)%m==m-1)
                sum=max(0ll,sum);
        }
    }
    cout<<ans<<"\n";
    return 0;
}
           

方法2

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+10;

int n,m,k;
ll a[maxn];
ll dp[maxn][20];

int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=0;i<=n;++i)
		for(int j=0;j<=m-1;++j)
			dp[i][j]=-9e18;
	dp[0][m-1]=0;
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<m;++j)
		{
			if(j==0) dp[i][j]=max(dp[i-1][m-1]+a[i]-k,a[i]-k);
			else dp[i][j]=dp[i-1][j-1]+a[i];
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<"\n";
	return 0;
}
           

方法3

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+10,mod=1e9+7;

int n,m,k;
int a[maxn];
ll dp[maxn];

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<n;++i) cin>>a[i];
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        ll s=0;
        for(int j=i-1;j>=max(0,i-m);--j)
        {
            s+=a[j];
            dp[i]=max(dp[i],dp[j]+s-k);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans<<"\n";
    return 0;
}