【蓝桥杯3535】数组分割（三种方法）（动态规划&规律&java）

问题描述

输入输出

题目分析

题目说了一大堆，其实意思就是：给你一个数组，你需要把数组拆分成两半，并且每一半的所有数的总和需要为偶数（若数为0则总和视为0，也是偶数）。

方法一 动态规划——数&总和（未通过）

首先想到的是将可选的数作为行，所选的数之和为列，进行动态规划。

推导出的公式为dp[i][j] = dp[i – 1][j] + dp[i – 1][j – nums[i]]。

但是这样有缺陷，因为是以所选的数之和为列，但是根据题目给出的数据范围，这个总和可能会很大很大，超出数组所能开出的最大范围，即int表示的最大值。

因此这个方法只在小规模数据可用，数据大了就不行了。

方法一 代码

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int t = scanner.nextInt();

		while (t-- > 0) {
			int n = scanner.nextInt();
			int all = 0; // 总和
			int[] nums = new int[n + 1]; // 存储可选的数

			for (int i = 1; i <= n; i++) {
				nums[i] = scanner.nextInt();
				all += nums[i];
			}

			// 若总和为奇数，无法分割
			if (all % 2 == 1) {
				System.out.println(0);
				continue;
			}

			arraySplit(n, all, nums);
		}
	}

	public static void arraySplit(int n, int all, int[] nums) {
		int[][] dp = new int[n + 1][all + 1]; // dp[i][j]表示有i个数可取，且总和为j
		for (int i = 0; i <= n; i++) { // 初始化
			dp[i][0] = 1;
		}

		int allNow = 0;// 记录当前可以选的数的总和
		for (int i = 1; i <= n; i++) {
			allNow += nums[i]; // 作用是限制后面当前行的计算范围，减少不必要的计算
			for (int j = 1; j <= all; j++) {
				if (j <= allNow) {
					if (j >= nums[i]) {
						dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
					} else {
						dp[i][j] = dp[i - 1][j];
					}

				}
			}
		}

		int ans = 0;
		for (int j = 0; j <= all; j++) {	//将最后一行总和为偶数的列的值相加
			if (j % 2 == 0) {
				ans = (ans + dp[n][j]) % 1000000007;
			}
		}

		System.out.println(ans);
	}
}

方法二 动态规划——数&子集个数（通过）

方法二是对方法一的优化，将列改为了对总和为奇数/偶数的个数。

最终的结果就是dp[n][0]（n为可选的个数），比如下面的dp[7[0]=64，dp[2][0]=4。

方法二 代码

import java.util.Scanner;

public class Main {
	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数组，行代表数，列代表总和为奇数或偶数

			// 初始化
			dp[0][0] = 1;
			dp[0][1] = 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]);
		}
	}
}

方法三 数学规律（通过）

由方法二的过程推导中其实可以看出一个数学规律。

首先来看可选的数，要么是偶数，要么是奇数。

每个数有选和不选两种情况，那么n个数总共就有2的n次方种情况。

根据题意，要拆分使得两组的总和均为偶数。我们从小看起，要满足这个条件，可以是任意个偶数，也可以是任意一对（两个）奇数。

方法三 代码

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int t = scanner.nextInt();
		while (t-- > 0) {
			int n = scanner.nextInt();
			int oddNum = 0, evenNum = 0; // 奇数个数、偶数个数

			for (int i = 0; i < n; i++) {
				int k = scanner.nextInt();

				// 记录奇数和偶数的个数
				if (k % 2 == 1) {
					oddNum++;
				} else {
					evenNum++;
				}
			}

			// 若奇数个数不为偶数，不存在解
			if (oddNum % 2 == 1) {
				System.out.println(0);
				continue;
			}

			// 计算并输出
			int ans;
			if (oddNum == 0) {// 如果全是偶数
				ans = (int) (Math.pow(2, evenNum) % 1000000007);
			} else {
				ans = (int) (Math.pow(2, evenNum + oddNum - 1) % 1000000007);
			}

			System.out.println(ans);
		}
	}
}

相关知识 

动态规划的设计以及优化

（by 归忆）