一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 958C2 - Codeforces

---

二、解题报告

1、思路分析

明显的dp

我们可以写一个会超时的朴素dp

状态定义

f[i][j]为前i个数字，划分为j组的最大收益

那么f[i][j] = max{ f[x][j - 1] + sum(x + 1, i) % P }

我们发现状态转移的值跟模P有关

换言之，我们不关心具体的区间和的值为多少，我们只关心区间和对P取余是多少

我们改进状态

f[i][j]为前缀和对P取余为j时，划分为i组的最大收益，那么

f[i + 1][j] = max{ f[i + 1][j], f[i][x] + (j - x) % P }

2、复杂度

时间复杂度： O(NKP)空间复杂度：O(KP)

3、代码详解

 ​

n, k, P = map(int, input().split())
a = list(x % P for x in map(int, input().split()))

fmax = lambda x, y: x if x > y else y

pre = 0
f = [[-P * k] * P for _ in range(k + 1)]
f[0][0] = 0

for i in range(n):
    pre = (pre + a[i]) % P

    for j in range(k - 1, -1, -1):
        for x in range(P):
            f[j + 1][pre] = fmax(f[j + 1][pre], f[j][x] + (pre - x) % P)


print(f[k][pre])