思路

01背包 + 同余定理

过程

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1e3 + 10, K = 1e3 + 10;
LL a[N], f[N][K];
int n, k;

int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 0;j < k;j ++)
        {
            f[i][j] = f[i - 1][j];
            f[i][j] = max(f[i - 1][(j - a[i] % k + k) % k] + a[i], f[i][j]);
        }
    }
    cout << (f[n][0] == 0 ? -1 : f[n][0]) << endl;
    return 0;
}