2144 砝码称重 2

 时间限制: 1 s

 空间限制: 16000 KB

 题目等级 : 钻石 Diamond

题解

题目描述 Description

有n个砝码,现在要称一个质量为m的物体,请问最少需要挑出几个砝码来称?

注意一个砝码最多只能挑一次

输入描述 Input Description

第一行两个整数n和m,接下来n行每行一个整数表示每个砝码的重量。

输出描述 Output Description

输出选择的砝码的总数k,你的程序必须使得k尽量的小。

样例输入 Sample Input

3 10 5 9 1

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

1<=n<=30,1<=m<=2^31,1<=每个砝码的质量<=2^30

分类标签 Tags 点此展开 

这个题,,

非常考研剪枝能力,

除了正常的最优性剪枝

还要用后缀和剪枝。

醉了醉了。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<map>
 7 #define lli long long int 
 8 using namespace std;
 9 void read(lli &n)
10 {
11     char c='+';lli x=0;bool flag=0;
12     while(c<'0'||c>'9')
13     {c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')
15     {x=x*10+(c-48);c=getchar();}
16     flag==1?n=-x:n=x;
17 }
18 lli n,p;
19 lli a[10001];
20 lli sum2[10001];
21 map<int,bool>mp;
22 lli comp(lli a,lli b)
23 {
24     return a>b;
25 }
26 lli ans=0x7ffff;
27 void dfs(lli now,lli num,lli step,lli sum)
28 {
29     
30     if(step>ans||sum>p)
31         return ;
32     
33     if(sum==p)
34     {
35         ans=min(ans,step);
36         return ;
37     }
38     if(sum2[now]+sum<p)
39         return ;
40     if(now==n)
41         return ;
42     dfs(now+1,a[now+1],step+1,sum+a[now+1]);
43     dfs(now+1,num,step,sum);
44 }
45 int main()
46 {
47     read(n);read(p);
48     for(lli i=1;i<=n;i++)
49         read(a[i]);
50     sort(a+1,a+n+1,comp);
51     for(int i=n;i>=1;i--)
52         sum2[i]=sum2[i+1]+a[i];
53     for(lli i=1;i<=n;i++)
54         dfs(i,a[i],1,a[i]);
55     printf("%lld",ans);
56     return 0;
57 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python成长之路

集合常用操作

1664
来自专栏用户画像

C语言测试题

2. 假设已指定i为整型变量,f为float变量,d为double型变量,e为long型,有下面式子:

1705
来自专栏函数式编程语言及工具

Scala Macros - 元编程 Metaprogramming with Def Macros

    Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具,可以通过它来解决一些用普通编程或者类层次编程(type level pr...

2949
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》 附录A NumPy高级应用A.1 ndarray对象的内部机理A.2 高级数组操作A.3 广播A.4 ufunc高级应用A.5 结构化和记录式数组A.6 更多

在这篇附录中,我会深入NumPy库的数组计算。这会包括ndarray更内部的细节,和更高级的数组操作和算法。 这章包括了一些杂乱的章节,不需要仔细研究。 A.1...

6666
来自专栏西枫里博客

Python学习笔记十(lambda表达式)

lambda是一个表达式,并不像def一样定义一个复杂的函数,很简洁的一个代码块。通常被用来创建匿名函数。lambda的好处也很明显,首先省去了函数的定义过程,...

842
来自专栏伪君子的梦呓

题解 ~ 输出三个数中的最大值 ~ C++ 做法

2115
来自专栏游戏开发那些事

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

1174
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

2141
来自专栏开发技术

排序之冒泡排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

944
来自专栏Petrichor的专栏

tensorflow: Shapes and Shaping 探究

1001

扫码关注云+社区

领取腾讯云代金券