线性DP，状态优化，CF 958C2 - Encryption (medium)

本文主要是介绍线性DP，状态优化，CF 958C2 - Encryption (medium)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

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 ypre = 0
f = [[-P * k] * P for _ in range(k + 1)]
f[0][0] = 0for i in range(n):pre = (pre + a[i]) % Pfor 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])

这篇关于线性DP，状态优化，CF 958C2 - Encryption (medium)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---