解题思路:
注意事项:
将砝码独立来看,
在当前砝码称出重量x的情况下,对于砝码i都有三种操作:
x+砝码i的重量(放同侧)
x-砝码i的重量(放异侧)
x(不放)
显然前面两种操作才有可能产生不同的重量。
另外砝码i一定能称出其自身的重量
又考虑到set能够用于排除相等的元素
由于砝码称出的重量是正的,因此将操作获得的结果取绝对值再放入集合中
以上的图解只分析了两种情况 ,所有需要画出所有的情况,就会画出一颗树。
左子树代表选择放入新的砝码,右子树表示不放入新的砝码,也就是继承上次的重量。
注意:左子树可能会秤出两种重量
参考代码:
import java.util.*; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); Set<Integer> set = new HashSet<>(); int n = scan.nextInt(); int[] fama = new int[n]; for (int i = 0; i < n; i++) { fama[i] = scan.nextInt(); } //初始化set,表示一开始天平上没有砝码,重量为0 set.add(0); for (int i = 0; i < n; i++) { //在没放入新的砝码前,将秤得的所有重量放入list集合中 List<Integer> list = new ArrayList<>(set); for (int k : list) { //相加和相减取绝对值产生新的两个重量,并加重量放入set集合中 //注意:如果新秤得的重量在原来的set集合存在,将不被放入set中 set.add(k + fama[i]); set.add(Math.abs(k - fama[i])); } } //移除0元素 set.remove((Object)0); //输出set集合大小,即秤得的重量数 System.out.println(set.size()); } }
DP版本思路差不多
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //存放砝码重量 int a[] = new int[n]; int sum = 0; for(int i = 0; i < n; i++){ a[i] = sc.nextInt(); sum += a[i]; } int cnt = 0; boolean dp[][] = new boolean[n][sum+1]; dp[0][a[0]] = true; for(int i = 1; i < n; i++){ //将上一个状态复制过来 for(int j = 1; j <= sum; j++) dp[i][j] = dp[i-1][j]; dp[i][a[i]] = true; for(int j = 1; j <= sum; j++){ if(dp[i-1][j]){ dp[i][j+a[i]] = true; dp[i][Math.abs(j-a[i])] = true; } } } for(int i = 1; i <= sum; i++) if(dp[n-1][i]) cnt++; System.out.println(cnt); } }
0.0分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复