盾神与砝码称重

清疚 2022-07-12 12:13 138阅读 0赞

package 搜索;  
import java.io.IOException;  
import java.io.InputStream;  
import java.util.Arrays;  
  
  
/\*\*  
\*  
\* @author wc  
\*  
\*/  
public class 盾神与砝码称重 \{  
static class Scanner \{  
  
  
private InputStream is = System.in;  
  
  
public int nextInt() \{  
try \{  
int i;  
  
  
while ((i = is.read()) < 45 || i > 57) \{  
\}  
  
  
int mark = 1, temp = 0;  
  
  
if (i == 45) \{  
mark = -1;  
i = is.read();  
\}  
  
  
while (i > 47 && i < 58) \{  
temp = temp \* 10 + i - 48;  
i = is.read();  
\}  
  
  
return temp \* mark;  
\} catch (IOException e) \{  
e.printStackTrace();  
\}  
  
  
return -1;  
\}  
\}  
  
  
static int\[\] arr;  
static int temp\[\];  
  
  
public static void main(String\[\] args) \{  
Scanner sc = new Scanner();  
int n = sc.nextInt();  
int m = sc.nextInt();  
arr = new int\[n\];  
temp = new int\[n\];  
for (int i = 0; i < n; i++) \{  
arr\[i\] = sc.nextInt();  
\}  
temp\[0\] = arr\[0\];  
for (int i = 1; i < n; i++)  
temp\[i\] = temp\[i - 1\] + arr\[i\];  
  
Arrays.sort(arr);  
  
while (m-- > 0) \{  
System.out.println(dfs(sc.nextInt(), n - 1) ? "YES" : "NO");  
\}  
\}  
  
  
static boolean dfs(int weigh, int i) \{  
if (weigh == 0) \{  
return true;  
\}  
if (i < 0 || Math.abs(weigh) > temp\[i\]) \{// i<0省略策略，arr\[-1\]=0数组最低0，所以可以逆推，arr\[n\]=0  
return false;  
\}  
for (; i >= 0; i--) \{  
if (dfs(weigh - arr\[i\], i - 1) || dfs(weigh + arr\[i\], i - 1)) \{  
return true;  
\}  
\}  
return false;  
\}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，138人围观）

还没有评论，来说两句吧...

相关阅读

相关【蓝桥杯】砝码称重

[3417. 砝码称重 - AcWing题库][3417. _ - AcWing] 题意： ![29f26757e1174102b819a74e4f568b98.png][

以你之姓@/ 2024年03月30日 10:14/ 0 赞/ 18 阅读

相关 AcWing——砝码称重

[4942. 砝码称重 - AcWing题库][4942. _ - AcWing] 1、题目给定一个天平和 101 个砝码。 101 个砝码的重量依次为 n⁰,n¹

比眉伴天荒/ 2023年09月27日 18:16/ 0 赞/ 73 阅读

相关 java能做称重软件_java实现砝码称重

5个砝码用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量(

╰半夏微凉°/ 2022年11月09日 01:27/ 0 赞/ 112 阅读

相关华为OJ称砝码

问题描述：现有一组砝码，重量互不相等，分别为m1、m2……mn；他们可取的最大数量分别为x1、x2……xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的重量

分手后的思念是犯贱/ 2022年10月01日 00:48/ 0 赞/ 133 阅读

相关称砝码问题

题目描述有一组砝码，重量互不相等，分别为 m1 、 m2 、 m3……mn ；它们可取的最大数量分别为 x1 、 x2 、 x3……xn 。现要用这些砝码去称

一时失言乱红尘/ 2022年08月08日 05:15/ 0 赞/ 154 阅读

相关 [编程题]称砝码

> Talk is cheap, show me the code. 一、问题描述现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；每种砝码对应的

太过爱你忘了你带给我的痛/ 2022年07月13日 03:21/ 0 赞/ 159 阅读

相关盾神与砝码称重

package 搜索; import java.io.IOException; import java.io.InputStream; import java.ut

清疚/ 2022年07月12日 12:13/ 0 赞/ 139 阅读

相关算法提高盾神与砝码称重

问题描述　　有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品

╰半夏微凉°/ 2022年06月15日 04:51/ 0 赞/ 147 阅读

相关 Java 盾神与砝码称重

问题描述　　有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物

电玩女神/ 2022年04月23日 01:30/ 0 赞/ 150 阅读

相关蓝桥杯--砝码称重（dp）

砝码称重 [题目评测][Link 1] 你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。请你计算一共可以称出多少种不同的

雨点打透心脏的1/2处/ 2021年07月16日 16:10/ 0 赞/ 373 阅读