1234. 倍数问题

题意

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。
数据保证一定有解。
思路

背包问题不要光硬套体积和价值，先定好状态，然后对其进行分析

优化：
- 1、由于第i层只用到第i - 1层，于j - 1 严格小于j，并且需要用到上一轮的数据，因此需要j从大到小遍历到1，因此可以优化到二维
- 2、贪心：余数相同时取数组较大的数，因此分别将余数是0到k - 1的最大3个数挑出来处理即可，最多挑出3 * 1000个数进行处理

代码

'''
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])