商场购物 - 最大化愉悦值且满足条件

{"title":"题目描述\n你来到了一个商场, 现在有 \nn 件你心仪的商品, 但是你又囊中羞涩, 已知每件商品有一个属性, \nxi表示愉悦值. 现在你想恰好购买 \nm 件商品, 使得愉悦值之和恰好是 \nc 的倍数, 并且愉悦值尽可能的大.\n\n数据格式\n输入格式\n第一行三个整数 \nn,m,c, 表示商品数量, 购买数量, 以及题干中的 c\n第二行 n 个整数 xi\n输出格式\n输出一个整数, 表示满足条件的最大愉悦值, 如果无法满足条件, 则输出 -1\n给出动态规划思路内容：动态规划思路如下：\n\n1. 定义状态：dp[i][j] 表示前 i 件商品中选择 j 件商品的情况下，愉悦值之和模 c 的余数的最大值。\n\n2. 初始化状态：dp[0][0] = 0，表示前 0 件商品选择 0 件商品时，愉悦值之和模 c 的余数为 0。\n\n3. 状态转移方程：对于第 i 件商品，有两种情况：\n\n a. 不选择第 i 件商品：dp[i][j] = dp[i-1][j]，表示前 i-1 件商品选择 j 件商品时，愉悦值之和模 c 的余数的最大值与前 i 件商品选择 j 件商品时的最大值相同。\n\n b. 选择第 i 件商品：dp[i][j] = max(dp[i-1][j-1] + xi[i] % c, dp[i-1][j])，表示前 i-1 件商品选择 j-1 件商品时，再选择第 i 件商品，愉悦值之和模 c 的余数的最大值与前 i 件商品选择 j 件商品时的最大值的较大值。\n\n4. 最终结果：dp[n][m]，表示前 n 件商品选择 m 件商品时，愉悦值之和模 c 的余数的最大值。\n\n时间复杂度分析：\n状态的数量为 O(nm)，状态转移的时间复杂度为 O(1)，所以总时间复杂度为 O(nm)。\n\n代码示例：\n\npython\ndef max_happiness(n, m, c, xi):\n dp = [[-1] * (m+1) for _ in range(n+1)]\n dp[0][0] = 0\n\n for i in range(1, n+1):\n for j in range(m+1):\n dp[i][j] = dp[i-1][j]\n if j > 0:\n dp[i][j] = max(dp[i][j], (dp[i-1][j-1] + xi[i-1] % c) % c)\n\n return dp[n][m] if dp[n][m] != -1 else -1\n\nn, m, c = map(int, input().split())\nxi = list(map(int, input().split()))\n\nprint(max_happiness(n, m, c, xi))\n\n\n注意：在计算 dp[i][j] 时，需要对结果取模 c。