蓝桥杯---数组分割

https://www.dotcpp.com/oj/problem3171.html

测试用例分析：

2
2
6 6
2
1 6

这代表有两个测试用例。

第一测试用例:

• 数组: [6, 6]
• 长度: 2

分析

• 数组中的所有元素都是偶数，因此任意组合的和都将是偶数。
• 可能的组合及其和：
  • 空集: 和 = 0 (偶数)
  • {6}: 和 = 6 (偶数)
  • {6}: 和 = 6 (偶数)
  • {6, 6}: 和 = 12 (偶数)

在这种情况下，所有可能的子集的和都是偶数，包括空集。因此，所有四种可能的子集选择（包括空集）都符合要求。

第二测试用例:

• 数组: [1, 6]
• 长度: 2

分析

• 数组中的元素和为奇数（1 + 6 = 7），不可能将数组分割成两个和都是偶数的部分。
• 可能的组合及其和：
  • 空集: 和 = 0 (偶数)
  • {1}: 和 = 1 (奇数)
  • {6}: 和 = 6 (偶数)
  • {1, 6}: 和 = 7 (奇数)

对于这个数组，不可能找到一种分割方式，使得两个子集的和都是偶数。因此，没有符合条件的子集选择。

解释输出

根据以上分析，对于第一测试用例，所有4种子集都符合条件，输出应该是4。对于第二测试用例，因为无法将和分成两部分都是偶数，输出应该是0。

动态规划：能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

package 真题.第十四界;

import java.util.Scanner;

public class _01数组分割 {
    static int mod = 1000000007;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt(); // 测试用例的数量
        while (t-- > 0) {
            int n = scan.nextInt(); // 数组的长度
            long sum = 0; // 用于计算数组元素的总和
            long[] a = new long[n + 1]; // 存储数组元素

            for (int i = 1; i <= n; i++) {
                a[i] = scan.nextLong();
                sum += a[i]; // 累加求总和
            }

            // 如果总和是奇数，无法分割成两个和都为偶数的子集
            if (sum % 2 == 1) {
                System.out.println(0);
                continue;
            }

            long[][] dp = new long[n + 1][2]; // 动态规划数组
            dp[0][0] = 1; // 一个元素也不取时，偶数和为0的方案数是1
            dp[0][1] = 0; // 一个元素也不取时，奇数和的方案数是0

            for (int i = 1; i <= n; i++) {
                if (a[i] % 2 == 0) { // 当前元素为偶数
                    dp[i][0] = (dp[i - 1][0] * 2) % mod; // 偶数加偶数还是偶数
                    dp[i][1] = (dp[i - 1][1] * 2) % mod; // 偶数加奇数还是奇数
                } else { // 当前元素为奇数
                    dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod; // 奇数加偶数变奇数，奇数加奇数变偶数
                    dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod; // 同上，反向
                }
            }
            System.out.println(dp[n][0]); // 输出偶数和的方案数
        }
    }
}