codeforces:dp专练【关于子数组求和 + 选or不选来dp + 二维dp】

题目1：较简单

分析

在长度为n的数组中取k个长度为m的子数组，然后让他们的和最大
这里有两个变量：一个是多少个子数组，一个是多长的数组
所以dp[i][j] => first j elements pick i groups 的最大值
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])
可以用前缀和优化

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

题目2：较难

分析

从长度为n的数组里面选数组，长度分别是k k - 1 … 1 然后这些子数组的和是越来越大的
同样的，我们想要这个k更大，我们就需要选数量小的子数组时的和最大 这样才能给后面更大的取值空间
为了从小到大考虑，我们倒过来，考虑数组长度从1到k的，然后dp[i][j]还是前j个元素取i组，这次记录的是最后一组的最大和
也是分取或者不取a[j] 不取好办
取得话，我们就能把当前第i组得和求出来
然后跟前j - i个元素的i - 1组的最大和比比，看看能不能比它小即可
如果能的话就是取 要a[j]和不要a[j]的最大值 同时ans = max(ans, i)

ac code

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

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    # max k: (k + 1) * k // 2 <= n, k ^ 2 + k - 2n = 0
    maxn = int((-1 + sqrt(1 + 8 * n)) / 2)
    # we consider len from 1 ... k
    # and if we get every sum of subarray as large as possible
    # the more groups we can choose
    # cause sum(array i) > sum(array i + 1)
    # but len(array i) = i, len(array i + 1) = i + 1
    a = a[::-1]
    preSum = list(accumulate(a, initial = 0))
    # dp[i][j]: first j elements from a and the ith group subarray
    # we want to get its max value
    dp = [[0] * (n + 1) for _ in range(maxn + 1)]
    # if we only choose one element, the max one we met
    for j in range(1, n + 1):
        dp[1][j] = max(dp[1][j - 1], a[j - 1])

    ans = 1
    # normal case
    for i in range(2, maxn + 1):
        for j in range(i * (i + 1) // 2, n + 1):
            # not choose a[j]
            dp[i][j] = dp[i][j - 1]
            # choose a[j] as the last on of the group i
            # so we can get the sum of the group i
            group_i_sum = preSum[j] - preSum[j - i]
            # if it meet the requirement
            if group_i_sum < dp[i - 1][j - i]:
                ans = max(ans, i)
                dp[i][j] = max(dp[i][j], group_i_sum)

    print(ans)
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
27
28
29
30
31
32
33
34
35
36
37
38
39

总结

从长度为n的数组里面分i组 我们可以考虑前j个元素递归
如果有额外关系的话要额外判断
然后前缀和可以优化
特别地，这种题的思路都是选还是不选