https://codeforces.com/contest/1197

D. Yet Another Subarray Problem

 

题意：给定一个数组，和m，k。问所有区间的 ∑i=lrai−k⌈r−l+1m⌉\sum\limits_{i=l}^{r} a_i - k \lceil \frac{r - l + 1}{m} \rceil 的最大值。1≤n≤3⋅105,1≤m≤10,1≤k≤1091 \le n \le 3 \cdot 10^5, 1 \le m \le 10, 1 \le k \le 10^9

dp

从m的范围应该要想到对m的模作为dp的一维。

dp[i][j]dp[i][j] 表示以 i 为右端点，长度对m的模为 j 的区间的最大值。

则当模从0变为1时，⌈r−l+1m⌉\lceil \frac{r - l + 1}{m} \rceil 的值+1，这时的值为模为0时的值 -k。

其它时候直接+a[i]。

转移方程为：

dp[i][j]=dp[i−1][(j−1+m)%m]+a[i],(j!=1)dp[i][1]=dp[i−1][0]+a[i]−kdp[i][j]=dp[i-1][(j-1+m)\%m]+a[i], (j!=1)\\ dp[i][1]=dp[i-1][0]+a[i]-k\\

注意m=1时的特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 3e5 + 10;
int n, m;
ll k, a[N];
ll dp[N][20], ans;
int main() {
	scanf("%d%d%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 = 1; j < m; j++)dp[i][j] = -inf;
	dp[1][1 % m] = max(dp[1][1 % m], a[1] - k);
	for (int i = 2; i <= n; i++) {
		dp[i][1 % m] = max(dp[i - 1][0] + a[i] - k, a[i] - k);
		for (int j = 2; j < m; j++) {
			dp[i][j] = dp[i - 1][j - 1] + a[i];
		}
		if (m != 1)dp[i][0] = max(dp[i][0], dp[i - 1][m - 1] + a[i]);
	}
	for (int i = 1; i <= n; i++)for (int j = 0; j < m; j++)ans = max(ans, dp[i][j]);
	printf("%lld\n", ans);
	return 0;
}