[wikioi2144]砝码称重2(另类的dfs)

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

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

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

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

3 10
5
9
1

2

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

时间限制:1S 空间限制:16MB

分析:首先注意到这本是DP题,然后看见n和m的范围又很快意识到这肯定是搜素,如果深搜的话,2^30要TLE,但是如果BFS的话,那个该死的空间限制16MB……

常规思路啪啪啪不行!(出题人请再打我一次)

然后人类很聪明……类似双向BFS的双向DFS出世了……就是对前面一半的数dfs出他们能组合出的各种数值及对应的最小个数(map轻易办到……),对后面一半是同理处理,然后就是两个集合枚举遍历找啊找就行了……

真是Orz……

[wikioi2144]砝码称重2(另类的dfs)

上一篇:String 值传递or引用传递


下一篇:浅谈OSI七层架构模型1