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;
}