主页

洛谷题解 P5020 【货币系统】

题目链接

这是一篇85分的题解

思路:

  • 虽然我考场上没有看懂题意,但这并不妨碍我们通过研究样例,发现实际上就是去掉可以被分解为小数的大数。

样例1:

3 19 10 6 去掉6 = 3 * 2,去掉19 = 10 + 6 + 3 。

  • 既然如此我们便将这些数字排序,最小的肯定不能被去掉,我们从第二位开始,依次dfs试图将其用小的数字表示出来。。。

接下来是代码

阅读更多

洛谷题解 P1441 【砝码称重】

题目链接

DP是不可能DP的,这辈子不可能DP的,只有打打模拟队列才能维持的了生活的样子,DP超难调的,一点都不好玩(还是要学的23333

在经历了二维dp调不好,一维dp看不懂,bitset啥玩意的懵⚪之后,我决定尝试一下模拟这个过程。。。

感谢@WLZS 提供的深搜剪枝思路,出现了60->AC的奇迹。

说一说思路吧,

  1. 深搜全排列去掉砝码(记得剪枝变成组合否则60分TLE)
  2. 砝码称重过程:
    1. 找到一个没有去掉的砝码,加入队列
    2. 拿一个砝码,和已经加入队列的重量相加,最后自己加入队列(想一想为什么不先加入队列)
    3. 重复上一步,加完后更新答案的值

以下为代码部分

阅读更多