1234. 倍数问题
摘要
Title: 1234. 倍数问题
Tag: 背包问题、贪心、dp
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1234. 倍数问题
-
题意
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。
数据保证一定有解。 -
思路
背包问题不要光硬套 体积和价值，先定好状态，然后对其进行分析
优化：
- 1、由于第i层只用到第i - 1层，于j - 1 严格小于j，并且需要用到上一轮的数据，因此需要j从大到小遍历到1，因此可以优化到二维
- 2、贪心：余数相同时取数组较大的数，因此分别将余数是0到k - 1的最大3个数挑出来处理即可，最多挑出3 * 1000个数进行处理
-
代码
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'''
Author: NEFU AB-IN
Date: 2022-04-06 17:46:30
FilePath: \ACM\Acwing\1234.py
LastEditTime: 2022-04-06 20:18:19
'''
INF = int(1e10)
N = int(1e3 + 10)
dp = [[-INF] * N for _ in range(4)]
g = [[] for _ in range(N)]
n, K = map(int, input().split())
a = list(map(int, input().split()))
for i in a:
g[i % K].append(i)
dp[0][0] = 0
for i in range(K):
g[i].sort(reverse=True)
for u in range(min(3, len(g[i]))):
x = g[i][u]
for j in range(3, 0, -1):
for k in range(K):
dp[j][k] = max(dp[j][k], dp[j - 1][(k - x) % K] + x)
print(dp[3][0])
