题解 | 小红取数

挣牛币用...

动态规划

初始化是这样的，转移方程是那样的，然后就能求出结果了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e13;
signed main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (auto& i : arr) {
        cin >> i;
    }
    vector<vector<int>> dp(n, vector<int>(k, -1));
    dp[0][arr[0] % k] = arr[0];
    for (int i = 1; i < n; ++i) 
    {
        int t = arr[i] % k;
        dp[i] = dp[i - 1];
        dp[i][arr[i] % k] = max(dp[i][arr[i] % k], arr[i]);
        for (int j = 0; j < k; ++j)
        {   
            int tt = dp[i - 1][(j - t + k) % k];
            if (tt != -1)
                dp[i][j] = max(dp[i][j], tt + arr[i]);
        }
    }
    cout << dp[n - 1][0];
}
// 64 位输出请用 printf("%lld")