适合dfs而不适合dp的情况

女爷i 2024-03-25 03:33 83阅读 0赞

HJ93 数组分组 牛客

输入int型数组，询问该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），不是5的倍数也不是3的倍数能放在任意一组，可以将数组分为空数组，能满足以上条件，输出true；不满足时输出false。

#### 输入描述： ####

第一行是数据个数，第二行是输入的数据

#### 输出描述： ####

返回true或者false

### 示例1 ###

输入：

4
    1 5 -5 1

复制输出：

true

复制说明：

第一组：5 -5 1
    第二组：1

思路很简单，就是将3的倍数，5的倍数，以及即不是3的倍数，又不是5的倍数的分别放在3个数组中，然后求出总和，如果总和奇数，直接返回false，否则 target = sum / 2 if sum / 2 - sum3 == sum5 存在，则可以组成，否则不能。这里对于含有正负两种数值的数组组合求特定值，不太适合用dp因为比较复杂，写了好久。。。。没成功。

还是dfs吧

import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                LinkedList<Integer> list = new LinkedList<>();
                int n = in.nextInt();
                int sum5 = 0;
                int sum3 = 0;
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    int cur = in.nextInt();
                    if (cur % 5 == 0) {
                        sum5 += cur;
                    } else if (cur % 3 == 0) {
                        sum3 += cur;
                    } else {
                        list.add(cur);
                    }
                    sum += cur;
                }
                int target = sum / 2 - sum3;
                if (sum % 2 != 0) System.out.println("false");
                else System.out.println(helper(list, target));
            }
        }
        private static boolean helper(LinkedList<Integer> list, int target) {
            return helper(0, list, target);
        }
        private static boolean helper(int l, LinkedList<Integer> list, int target) {
            if (l == list.size()) return target == 0;
            return helper(l + 1, list, target - list.get(l)) || helper(l + 1, list, target);
        }
    }