题解 | #小红取数#

思路解析： 如何想到动态规划的递推式是最重要的。

1.如果我们采取一维的数组，那么没法同时满足两个条件。所以采取二维数组进行数据的存储。

2.利用dp[i][j],将第一个i表示前i个数值，j表示前i个数值modk后的余数值。而dp[i][j]整体表示前i个数值在余j时的最大值，而我们需要获得的是dp[n][0]，即前n个数值，余0时的最大值。

3.dp[i - 1][j] + num[i]表示在前i-1个数的基础上，加入第i个数值时的最大值，那么此时的余数为(j + num[i]) % k,即dp[i][(j + num[i]) % k] = dp[i - 1][j] + num[i]。当然，这是将第i个数值加入时的最大值，若不加入时，是否存在更大的值，即dp[i][(j + num[i]) % k] = dp[i - 1][(j + num[i]) % k]。

#include<iostream>
using namespace std;
long long int num[1001],dp[1010][1010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    for(int i = 0;i < n;++i)
        cin >> num[i];
    for(int i = 0;i <= n;++i)
        for(int j = 0;j < k;++j)
            dp[i][j] = -1e18;
    dp[0][0] = 0;
    for(int i = 1;i <= n;++i)
        for(int j = 0;j < k;++j)
            dp[i][(j + num[i - 1]) % k] = max(dp[i - 1][j] + num[i - 1],dp[i - 1][(j + num[i - 1]) % k]);
    if(dp[n][0] <= 0)
        cout << -1;
    else
        cout << dp[n][0];
}