题解 | #小红取数#

/*
集合：前i个数组中选择一些数 并且 这些数的和必须是k的倍数的方案
属性：求最大
状态定义：dp[i][j]表示前i个数中，选择一些数的和对k取余为j
状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][(j+nums[i])%k]+nums[i])
*/
import java.util.Scanner;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long a[] = new long[n+1];
        for(int i=0; i<n; ++i){
            a[i] = sc.nextLong();
        }
        long dp[][] = new long[n+1][k+1];
        for(int i=0; i<=n; ++i) Arrays.fill(dp[i],-1);
        dp[0][0] = 0;
        for(int i=1; i<=n; ++i){
            for(int j=0; j<k; ++j){
                if(dp[i-1][j]!=-1) dp[i][j] = dp[i-1][j];
                int tmp = (int)(j - a[i - 1] % k + k) % k;
                if(dp[i-1][tmp]!=-1){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][tmp]+a[i-1]);
                }
            }
        }
        System.out.println(dp[n][0] == 0 ? -1 : dp[n][0]);
    }
}