小红取数

难度：3星

首先第一个想法是，开一个dp数组，$dp[i]dp[i]$ 代表取前i个数的最大值。

那么dp[i]怎么求呢？很明显，如果要取了第 $ii$ 个数 $a[i]a[i]$ ，满足和能被k整除，那么就有个限制：前i-1个数里，满足取的数之和除以k的余数为 $k-a[i]k-a[i]$ ，之后加上 $a[i]a[i]$ 才能正好被k整除。

所以一维数组是不够的，需要开二维数组：$dp[i][j]dp[i][j]$ 代表前 $ii$ 个数里面，取一些数，相加的和除以 $kk$ 的余数为 $jj$ 的最大值。

这样就得到转移方程：

$dp[i][(j+a[i])\mathrm{\%}k]=max(dp[i-1][j]+a[i],dp[i-1][(j+a[i])\mathrm{\%}k])dp[i][(j+a[i])\backslash \%k]=max(dp[i-1][j]+a[i],dp[i-1][(j+a[i])\backslash \%k])$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100100];
ll dp[1010][1010];
int main(){
    long long n,k,i,j;
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=0;i<=n;i++){
        for(j=0;j<k;j++){
            dp[i][j]=-1e18;
        }
    }
    dp[0][0]=0;

    for(i=1;i<=n;i++){
        for(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]);
        }
    }
    if(dp[n][0]<=0)cout<<-1;
    else cout<<dp[n][0];
}