蓝桥杯java-B组真题—动态规划

目录

一.什么是动态规划?

二.题目

第一种情况:集合本身之和为奇数

第二种情况:集合本身之和为偶数

下面是代码实现:

---

一.什么是动态规划?

这里就简单的解释一下，动态规划就是记录之前的计算结果，避免重复的计算之前已经计算过的结果，用空间换取时间的一种方法

二.题目

通过题目我们可以知道是要求计算有多少子集，补集之和是偶数的问题，首先我们就需要考虑什么情况下子集，补集之和可以是偶数

集合之和 = 子集之和+补集之和

第一种情况:集合本身之和为奇数

集合本身之和为奇数说明集合中存在奇数个奇数，那么无论怎么组合补集和子集之和都不可能同时为偶数，这种情况直接输出0即可

第二种情况:集合本身之和为偶数

集合本身之和为偶数说明集合中要么没有奇数，要么奇数个数为偶数

在分析完题目之后我们思考解题思路:

可以通过暴力循环算出，但是我们每一次循环都需要重复计算当前第i个元素之前有多少种符合要求的子集，这样时间复杂度肯定是不能通过了，思考到这里我们就知道这道题可以使用动态规划的思想去解决，用一个数组来记录第i个元素前有多少种符合要求的子集，然后去思考之前的结果加上第i个元素会有什么变化，写出状态方程这道题目就解决了

下面是代码实现:

public class Main {public static final long mod = 1000000007L;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int x = scan.nextInt();while(x>0){int n = scan.nextInt();long[] a = new long[n];//存储数组;long sum = 0;//记录前i个元素的和for(int i = 0;i<n;i++)//初始化数组{a[i] = scan.nextLong();sum += a[i];}x--;if(sum%2!=0)//说明和为奇数,子集,补集的和不可能都为偶数,集合中有奇数个奇数{System.out.println(0);continue;}long[][] b = new long[n+1][2];//动态规划数组//[i+1][0]代表前i个元素中有多少个偶数子集,[i+1][1]代表前i个元素有多少个奇数子集b[0][0] = 1;//空集时和为0,0为偶数b[0][1] = 0;for(int i = 0;i<n;i++)//当集合的和为偶数{if(a[i]%2 == 0){b[i+1][0] = (b[i][0]*2)%mod;//动态规划数组转移方程b[i+1][1] = (b[i][1]*2)%mod;}else{b[i+1][0] = (b[i][0]+b[i][1])%mod;b[i+1][1] = (b[i][0]+b[i][1])%mod;}}b[n][0] = b[n][0]%mod;System.out.println(b[n][0]);}scan.close();}
}

这里也可以使用单个变量来记录符合要求的子集，不过用数组来写逻辑更加清晰

三.执行结果