题解 | #小红取数#

#include <iostream>
#include <bits/stdc++.h> // 包含所有标准库
using namespace std;

int main() {
    int n, k; // n 表示数组的大小，k 表示取模的值
    long long arr[1001]; // 存放输入的数组
    cin >> n >> k; // 输入 n 和 k
    for(int i = 1; i <= n; i++) {
        cin >> arr[i]; // 输入数组的元素
    }

    long long dp[1001][1001] = {0}; // 初始化动态规划数组，默认为 0

    // 遍历数组的每个元素
    for(int i = 1; i <= n; i++) {
        // 先复制前一天的状态
        for(int j = 0; j < k; j++) {
            dp[i][j] = dp[i - 1][j];
        }
        // 更新动态规划数组
        for(int j = 0; j < k; j++) {
            int l = (dp[i - 1][j] + arr[i]) % k; // 计算新的取模值
            dp[i][l] = max(dp[i - 1][l], dp[i - 1][j] + arr[i]); // 更新最大值
        }
        // 可以通过下面的注释部分来调试输出每一行的 dp 数组
        // for(int j = 0; j < k; j++)
        //     cout << dp[i][j] << " ";
        // cout << endl;
    }

    int ans = -1; // 初始化答案为 -1
    if(dp[n][0] != 0) { // 如果 dp[n][0] 不为 0
        cout << dp[n][0]; // 输出 dp[n][0] 的值
    } else {
        cout << -1; // 否则输出 -1
    }

    return 0;
}
// 64 位输出请用 printf("%lld")