题解 | 小红取数

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N  = 1e3 + 1;
ll n,k,dp[N][N],a[N];

int main(){
    cin>>n>>k;
    for(int i = 1;i<=n;i++) cin>>a[i];

    for(int i = 0;i<=n;i++) {
        for(int j = 0;j<k;j++) dp[i][j] = -1e18;
    }

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

    return 0;
}

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344