题解 | 小红取数

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e3 + 5;
int f[MAXN],dp[MAXN][MAXN];;

signed main()
{
    int n, k; cin >> n >> k;
    //对第一层初始化一下
    for(int i = 0; i <= n; i++) dp[0][i] = -1e18;
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)cin >> f[i];

    //当f[i]余数是j时，需要找之前应该补的数,没有的话就直接继承上一层
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= k; j++)
            dp[i][j] = max(dp[i-1][j], dp[i-1][(f[i] + j)% k] + f[i]);

    if(dp[n][k])cout << dp[n][k];//有就输出没有就输出-1
    else cout << -1;
    return 0;
}