codeforces：C. George and Job【二维dp + 前j个选i组双变量类型 + 选or不选】

分析

这里的话，我们要求的是n个元素里面选k组，每组m个，这样的话能够达到的最大元素和
乍一看，没啥思路的
这时候试试用dp（对于这种多个里面选多个的，可以选or不选，涉及到递推关系）
我们设dp[i][j]为前j个元素里面选i个组的最大值
那么dp[i][j]怎么过来呢，分两种情况：
not choose a[j]: dp[i][j] = dp[i][j - 1]
choose a[j]: as the last element of group i, dp[i][j] = dp[i - 1][j - m] + (a[j - m + 1] + … + a[j])
不选的比较好理解
选了的话就a[j]作为最后一组的最后一个，最后一组的话我们选后m个（注意j大于等于m才行）
这样我们就可以得到最后一组的和，然后递归到i - 1组以及前j - m个元素即可

ac code

import sys
from itertools import accumulate
input = sys.stdin.readline

n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
preSum = list(accumulate(a, initial = 0))

# dp[i][j] => first j elements pick i groups
dp = [[0] * (n + 1) for _ in range(k + 1)]
# cal dp[i][j]: choose a[j] or not choose a[j]
# not choose a[j]: dp[i][j] = dp[i][j - 1]
# choose a[j]: as the last element of group i, dp[i][j] = dp[i - 1][j - m] + (a[j - m + 1] + ... + a[j])
for j in range(1, n + 1):
    for i in range(1, k + 1):
        # not choose a[j]
        dp[i][j] = dp[i][j - 1]
        # choose a[j] as the last element of group i
        if j >= m:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - m] + preSum[j] - preSum[j - m])

print(dp[-1][-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

这种dp[i][j]
前j个里面选i组，这种奇怪的思路