徐州经济开发区网站,范县网站建设,网站建设数据库配置,四川城乡与建设厅网站[蓝桥杯 2021 省 AB] 砝码称重
题目描述
你有一架天平和 N N N 个砝码, 这 N N N 个砝码重量依次是 W 1 , W 2 , ⋯ , W N W_{1}, W_{2}, \cdots, W_{N} W1,W2,⋯,WN 。 请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
输入格式
输入的第一…[蓝桥杯 2021 省 AB] 砝码称重
题目描述
你有一架天平和 N N N 个砝码, 这 N N N 个砝码重量依次是 W 1 , W 2 , ⋯ , W N W_{1}, W_{2}, \cdots, W_{N} W1,W2,⋯,WN 。 请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N N N 。
第二行包含 N N N 个整数: W 1 , W 2 , W 3 , ⋯ , W N W_{1}, W_{2}, W_{3}, \cdots, W_{N} W1,W2,W3,⋯,WN 。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
3
1 4 6样例输出 #1
10提示
【样例说明】
能称出的 10 种重量是: 1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11 1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11 1、2、3、4、5、6、7、9、10、11 。 1 1 2 6 − 4 ( 天平一边放 6 , 另一边放 4) 3 4 − 1 4 4 5 6 − 1 6 6 7 1 6 9 4 6 − 1 10 4 6 11 1 4 6 \begin{aligned} 11 \\ 26-4(\text { 天平一边放 } 6, \text { 另一边放 4) } \\ 34-1 \\ 44 \\ 56-1 \\ 66 \\ 716 \\ 946-1 \\ 1046 \\ 11146 \end{aligned} 1126−4( 天平一边放 6, 另一边放 4) 34−14456−166716946−1104611146
【评测用例规模与约定】
对于 50 % 50 \% 50% 的评测用例, 1 ≤ N ≤ 15 1 \leq N \leq 15 1≤N≤15 。
对于所有评测用例, 1 ≤ N ≤ 100 , N 1 \leq N \leq 100, N 1≤N≤100,N 个砝码总重不超过 1 0 5 10^5 105。
蓝桥杯 2021 第一轮省赛 A 组 F 题B 组 G 题。
import java.util.Scanner;public class Main {private static final int N 150000;//假设砝码总重量150000private static int n, sum, w;private static boolean[][] f new boolean[2][2 * N 1];//[天平][砝码重量]public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();
//f[i][j] 表示在使用前 i 个砝码的情况下能否称出重量为 j 的物品。f[0][N] true;//表示不使用任何砝码时可以称出 0 克的重量for (int i 1; i n; i) {//遍历砝码w scanner.nextInt();sum w;for (int j -sum; j sum; j) {//遍历砝码重量区间//i % 2 是为了在每次迭代过程中交替使用两个子数组实现所谓的“滚动数组优化”减少内存消耗//在当前考虑到了前 i 个砝码的情况下能否组合出重量为 j 的物体f[i % 2][j N] f[(i - 1) % 2][j - w N] || f[(i - 1) % 2][j w N] || f[(i - 1) % 2][j N];}}int ans 0;for (int i 1; i sum; i) {if (f[n % 2][i N]) {ans;}}System.out.println(ans);}
}
