目录
1.题目内容及其链接
2.题目分析
3.动态规划思路
4.dp初始化
5.可运行的代码和总结
1.题目内容及其链接
点击链接即可做题：数组分割
2.题目分析
该题的意思是将一个大集合A分为一个子集R1和补集R2，要求两个集合所有的元素和S1，S2必须都为偶数，求出有多少种R1，R2，因为S1,S2都为偶数，可以分析出A集合内所有元素和必然是偶数（两偶数和必然也为偶数），例如给R2分配一个空集显然S2=0，则S1的元素为A集合的所有元素和，S1为偶数所以A的所有元素和必然为偶数，如果A的所有元素和是奇数的话一定不能满足分成两个和为偶数的集合，所以我们可以在给A数组赋值的同时创建一个变量sum计算A的所有元素和，若为奇数则不需要向下计算了直接输出0,并且我们也不需要同时考虑R1和R2,那样会很麻烦，因为一个R1只会对应一个R2，并且在A集合元素和为偶数的情况下S1为偶数的话S2也必然为偶数，所以我们只需要考虑有多少种R1或R2的情况
3.动态规划思路
一个偶数可由一个偶数加上一个偶数或者一个奇数加上一个奇数得来，一个奇数只能有一个奇数加上一个偶数得来，所以我们可以定义一个二维的int的dp数组:dp[n+1][2],dp[i][0]表示前i个数元素和为偶数有多少种组合，反之dp[i][1]表示前i个数元素和为奇数有多少种组合，1.遍历到A[i+1]这个数时如果是偶数则更新dp[i+1][0]=dp[i][0]*2,假设A的前i个数有dp[i][0]个R1，遍历到A[i+1]为偶数，可以将A[i+1]这个元素添加到每一个前R1的后面于是可以有新组成了dp[i][0]个R1，同样的dp[i+1][1]=2*dp[i][1],因为偶数加奇数和仍然为奇数，2.当A[i+1]为奇数时，可以将A[i+1]这个元素添加到前i个元素和为奇数的集合后面时其元素和为偶数，再加上前i个素和为偶数的组合数，则dp[i+1][0]=dp[i][1]+dp[i][0],同理dp[i+1][1]=dp[i][0]+dp[i][1]具体状态转移代码如下;
if(nums[i]%2==0) {dp[i + 1][0]= dp[i][0] * 2 ;dp[i+1][1]=dp[i][1]*2;}else{dp[i+1][0]=dp[i][0]+dp[i][1];dp[i+1][1]=dp[i][0]+dp[i][1];}4.dp初始化
因为空集也算一个集合并且和为偶数0，所以初始化dp[0][0]=1,dp[0][1]=0,将其他都初始化为0，后续遍历更新。
5.可运行的代码和总结
import java.util.Arrays;import java.util.Scanner;public class Main { static int mod=(int) 1e9 + 7;public static void main(String[] args){ Scanner sc=new Scanner(System.in);int t=sc.nextInt();while(t>0){t--;int n=sc.nextInt();int nums[]=new int[n];int dp[][]=new int[n+1][2];dp[0][0]=1;//表示前i个数字有多少和为偶数的组合dp[0][1]=0;//表示前i个数字有多少和为奇数的组合long sum=0;for(int i=0;i<n;i++){nums[i]=sc.nextInt();sum+=nums[i];}if(sum%2==1) {System.out.println(0);continue ;//该情况已经不符合题意，继续while循环}for(int i=0;i<n;i++){if(nums[i]%2==0) {dp[i + 1][0]= dp[i][0]*2%mod;dp[i+1][1]=dp[i][1]*2%mod;}else{dp[i+1][0]=dp[i][0]+dp[i][1];dp[i+1][1]=dp[i][0]+dp[i][1];}dp[i+1][0]%=mod;dp[i+1][1]%=mod;}System.out.println(dp[n][0]);} }}对dp进行相加或者相乘时记得对mod取余，以防计算出来的值错误，该题虽然为编程题第一题，但也是技巧性挺强的一题，和往届C题都是送分的不同，说明蓝桥杯题越来越难了，下一届估计也差不多，不能掉以轻心，如果哪里解释不清楚的欢迎提问