还有比我菜的人吗？

分析

最难处理的地方在于 \(\Delta =k \lceil \frac{r-l+1}{m} \rceil\)。

设 \(g(x) = x \bmod m\)，首先这是个在非负整数域上周期为 \(m\) 的周期函数。循环节为 \([0,m-1]\)。其次在每一个周期中 \(g(x) \in [1,m-1]\) 的 \(x\) 与下一个周期 \(g(x)=0\) 的 \(x\)，\(\lceil \frac{x}{m} \rceil\) 的值都是相等的。这启发我们从区间长度模 \(m\) 的值下手。

设 \(f(r,k)\) 为右端点是 \(r\)，其左端点 \(l\) 满足 \(r-l+1 \bmod m = k\)。

考虑最特殊的 \(m=1\) 的情况，设区间长度为 \(len\)，上面那个式子永远是就是 $ k len$。当区间长度变为 \(len+1\)，右端点到 \(r+1\) 时，\(\Delta + k\)，整个式子增加 \(a_{r+1} -k\)。

当 \(m\) 是个一般数值时，就要用到取模了。设 \(len \bmod m = k\)，其中 \(k \neq m-1\) 且 \(k \neq 0\)，那么区间向右扩展到 \(r+1\) 时，只会增加 \(a_{r+1}\)，因为这是在 \(g(x)\) 的同一个周期内，\(\Delta\) 相同。 \[ f(r+1,k+1) = f(r,k)+a_{a_r+1} \quad k \in [1,m-2] \] 如果 \(k=m-1\)，那么 \(k+1 \mid m\)，进入下一个周期了。但是仍然相同，增加 \(a_{r+1}\)。 \[ f(r+1,k+1) = f(r,m-1) + a_{r+1} \quad k=m-1 \] 还有一种情况，当 \(k=0\) 时，可以“重新开启一段新区间”的。新区间的权值为 \(a_{r+1}-k\)。如果重启新区间，由上述讨论知道权值会增加 \(a_{r+1}-k\)。 \[ f(r+1,1) = \max{\{ f(r,0) + a_{r+1} ,a_{r+1}-k\}} \] 有意思的是，当 \(m=1\) 的时候，\(k\) 只能取 0，享受同级待遇。😅

CODE

上文为了方便叙述，转移用的是刷表法，代码里用的是填表法。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
const int N=3e5+10;
ll n, m, k, ans, a[N], f[N][20];
int main() {
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i) for(int j=0;j<m;++j) {
		if(j==1||m==1) f[i][j]=max(f[i-1][0]+a[i]-k,a[i]-k);
        // 特殊状态
		else if(!j) f[i][j]=f[i-1][m-1]+a[i];
        // j-1 mod m = m-1
		else f[i][j]=f[i-1][j-1]+a[i];
        // 一般状态
		ans=max(ans,f[i][j]);
	}
	printf("%lld\n",ans);
}