题解 | 小红取数

水题，考虑dp[i][j] 为：考虑到第 i 个数，模 k 余 j 的最大选数方案即可，转移是显然的，注意边界即可。

#include<bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, k;
    std::cin >> n >> k;

    std::vector<i64> a(n);
    for (auto &i : a) std::cin >> i;
    
    std::vector dp(n, std::vector<i64>(k, -2e18));
    dp[0][a[0] % k] = a[0];

    for (int i = 1; i < n; i++) {
        dp[i] = dp[i - 1];
        dp[i][a[i] % k] = std::max(dp[i][a[i] % k], a[i]);
        for (int j = 0; j < k; j++) {
            dp[i][(j + a[i]) % k] = std::max(dp[i][(j + a[i]) % k], dp[i - 1][j] + a[i]);
        }
    }

    std::cout << (dp[n - 1][0] > 0 ? dp[n - 1][0] : -1ll);

    return 0;
}

https://www.nowcoder.com/discuss/727521113110073344