题解 | #数组分组#

import java.util.Scanner;
import java.util.*;

// 据条件分组 + 01背包，求解背包凑成 target 的可能性
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int nums[] = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            System.out.println(confirm(nums));
        }
    }

    public static boolean confirm(int[] nums) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int num5 = 0;
        int num3 = 0;
        int offset = 0;
        int sum_max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 5 == 0) {
                num5 += nums[i];
            } else if (nums[i] % 5 != 0 && nums[i] % 3 == 0) {
                num3 += nums[i];
            } else {
                list.add(nums[i]);
                offset += nums[i] < 0 ? -nums[i] : 0;
                sum_max += Math.abs(nums[i]);
            }
        }
        int sum = 0;
        for (Integer item : list) sum += item;
        int cut = num5 - num3;
        if ((sum - cut) % 2 != 0) return false;
        int target = (sum - cut) / 2;
        return validate(list, target, offset, sum_max);
    }

    public static boolean validate(ArrayList<Integer> list, int target, int offset,
                                   int sum_max) {
        int base = 500;
        boolean[][] dp = new boolean[list.size() + 1][sum_max + 1];
        dp[0][offset] = true;
        for (int i = 1; i <= list.size(); i++) {
            for (int j = 0; j <= sum_max; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - list.get(i - 1) < 0 || j - list.get(i - 1) > sum_max) continue;
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - list.get(i - 1)];
            }
        }
        if (target + offset < 0 || target + offset > sum_max) return false;
        return dp[list.size()][target + offset];
    }
}