c++题解 | #小红取数#

dp[i][j] 表示前i个数字中取出的数的和，并且对k取余为j的最大值，答案就是dp[n][0]，表示对k取余为0的最大和。
整个dp初始化为-1： memset(dp, -1, sizeof(dp))
dp[0][0]初始化为0，表示前0个数取出的数的和是k的倍数的最大值为0；
1、 不取a[i]这个数的情况：当dp[i-1][j]!=-1，dp[i][j]=dp[i-1][j]；
2. 取a[i]：可以这样想，加上a[i]会导致dp[i][j]所有数的和对k取余有k种情况，所以枚举所有情况。dp[i][j] = dp[i-1][((j-a[i]%k)+k)%k]+a[i]和dp[i][j]的最大值。
这里((j-a[i]%k)+k)%k是因为c++种负数取余还会是负数，所以这样写。本质是遍历到加上a[i]整个和对k取余为j时，这种情况来自于 前一个i的 j-a[i]%k这种情况

#include <cstdio>
#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
typedef long long LL;
LL dp[N][N];  //dp[i][0] 表示a[i]
LL a[N];
int main() {
    int n,k;
    scanf("%d%d", &n,&k);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < k; j++){
            if (dp[i-1][j]!=-1)
                dp[i][j] = dp[i-1][j];
            int tmp = (((j-a[i])%k)+k)%k;
            if(dp[i-1][tmp] != -1)
                dp[i][j] = max(dp[i][j], dp[i-1][tmp]+a[i]);
        }
    }
    if (dp[n][0] == 0)
        printf("%d", -1);
    else
        printf("%lld", dp[n][0]);
    return 0;
}
// 64 位输出请用 printf("%lld")