蓝桥杯---数组分割
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]); // 输出偶数和的方案数
}
}
}
原文地址:https://blog.csdn.net/m0_74343360/article/details/137681593
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!