题解 | #小红取数#

看了大佬们写的没有看懂，自己写了半天，虽然是用时最多的还是要记录一下，并送给大家参考。

• 问题要点是dp数组如何构建、dp[i][j] 的含义、转移方程如何写。

1. dp数组如何构建：我以需计算的列表长度n为列，在此基础上添加一列辅助列，代表未取元素时的状态。以对数字K取模后的可能性为行，示例***5行。
2. dp[j][i] 的含义：在这个数组中，如果我们想确定最后一列即1结尾的最大模5的数我们就得先确定其前面5-1即模5 等于 4的数。可以看到，这些数是跳跃的，所以在依次遍历时我们要把每一列可以组成模5等于0-模5等于4的最大值列出来，方便下一列调用。所以dp[i][j]就表示，在列表中到第j个数可以组成的模5等于j的最大的值。例如dp[4][9]代表这列表4，8，2，9所组成的模5等于4的最大可能即8 + 2 + 9 = 19。
3. 转移方程:我写的比较复杂，主要思考是先把前列的值复制到本列，防止出现数值丢失。然后把前一列每一行逐个操作。用（当前的j加上前一列的模5等于0的最大值）去模5，与对应列的当前值比较。取大的填入当前值。例如dp[j][8]列的由来，先把0行2列的值赋予0行3列，再用0行2列的值与8组成的值进行模5等于3，所以把这个最大值与dp[3][2]值比较，找出较大的填入dp[3][2]。然后进行dp[1]行的处理。在处理到dp[4]行的时候把前一列的4复制到了本列，把4+8的结果填入了dp[3][2]。

• 当我们填好dp的时候第0行的最后一个数字就是我们要的结果。如果整行都是0则输出-1

while True:
    try:
        n, k = map(int, input().split())
        l = list(map(int, input().split()))
        dp = [[0 for i in range(n + 1)] for j in range(k)]
        for i in range(1, n + 1):
            for j in range(k):
                dp[j][i] = max(dp[j][i-1], dp[j][i])
                dp[(dp[j][i-1] + l[i-1]) % k][i] = max(dp[(dp[j][i-1] + l[i-1]) % k][i - 1], dp[j][i-1] + l[i-1])
        if dp[0][-1] == 0:
            print(-1)
        else:
            print(dp[0][-1])
    except:
        break