典型算法与ACM题目解析(3)—记忆化搜索的应用

桃扇骨 2022-09-19 12:25 84阅读 0赞

**典型算法与ACM题目解析(3)—记忆化搜索的应用**

//hudedi版

//pku 1351 numbers of locks

//maths problem ,Can I do it by scan??

//just have a try

//try and success

//value\[a\]\[b\]\[c\]\[d\],a表示还剩下几个，b表示已经找到了哪几个，用二进制表示

//c表示已经找到的最后一个数，d表示找到的书中有没有1，4

//相连的题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1351

题目描述　已知n个slots，n的范围为1-17每个slot有一个height，height的值有四种，分别为1,2,3,4。

问题：

给你n个slot的，必须满足以下两个条件：

一：必须有两个相邻的slot的差为3，即一个为4，一个为1，

二：必须有三种不同的height值的情况有多少种。

解答：

这种题目应该有组合数学公式，但公式会比较复杂，要推出来不容易，

而在一般的常规情况下，搜索是一种更常用的方法.

首先，分析时间复杂度，如果用暴搜的话，分一个slot有4种情况，这样时间复杂度就是4^16，显然是不可接受的，中间虽然有剪枝，但运行起来依然很慢，于是我们就采用记忆化搜索。

其次，我们确定需要记忆的状态。由于要满足两个条件，所以我们的记忆量也根据这两种情况确定。在搜索过程中，我们开一个数组来保存，保存量分别为还剩下几个slot;已经找到了哪几种height（只与种类有关，与量没关系），于是只有4种height，我们用二进制来;其中找到的是否满足第一个条件;所找到的量最后一个数是多少（这也会影响第一个条件）;

最后，当确定这些量之后，接下来要做的工作就非常简单了，直接搜就行了，在数据小于17的情况下，做不做其它剪枝都对速度影响不大了,在PKU上的运行时间也是0ms

附：

在pku上测试时,当n达到1000(实际上这个时候早已经超出int64的范围了，我们暂 不讨论这个)时都是0ms,当达到3500时也不过15ms(再加上一个剪枝)，而想再往上测时经超内存了.

如果谁有更好要或者更快的方法，请发出来一起学习(组合数学的公式就算了)

发表评论取消回复

表情：

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

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

相关阅读

相关典型算法与ACM题目解析(2)—有向图的强连通分量

典型算法与ACM题目解析(2)—有向图的强连通分量这道题是POJ的2186题，题意是说，有一群牛，总数为N(N<=10000),题目数据给出牛之间的关系，比如说1仰慕2，

古城微笑少年丶/ 2022年09月19日 12:25/ 0 赞/ 121 阅读

相关典型算法与ACM题目解析(3)—记忆化搜索的应用

典型算法与ACM题目解析(3)—记忆化搜索的应用 //hudedi版 //pku 1351 numbers of locks //maths problem ,Can I

桃扇骨/ 2022年09月19日 12:25/ 0 赞/ 85 阅读

相关典型算法与ACM题目解析(1)—寻找最大流的标号法

典型算法与ACM题目解析(1)—寻找最大流的标号法这种算法又叫Ford-Fulkerson算法，算法的核心思想是使用标号的方法不断寻找一个图上的可增广路径并且进行调整，直到

末蓝、/ 2022年09月19日 12:25/ 0 赞/ 118 阅读

相关记忆化搜索——滑雪

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 87592 Accepted: 32835 Des

女爷i/ 2022年08月21日 01:20/ 0 赞/ 193 阅读

相关 ural 1009 记忆化搜索

1009. K-based Numbers Time limit: 1.0 second Memory limit: 64 MB Let’s con

向右看齐/ 2022年08月09日 14:51/ 0 赞/ 164 阅读

相关 ACM 记忆化搜索 Function Run Fun & FatMouse and Cheese

滴，集训第四天打卡。今天是记忆化搜索和字典树... 记忆话搜索可以举一反三..字典树看了一下午几乎是绝望的.. 所以下一篇会是字典树专题... POJ 1579 Fu

ゝ一纸荒年。/ 2022年06月12日 09:36/ 0 赞/ 167 阅读

相关 Java实现记忆化搜索

记忆化搜索是在使用递归搜索或者类似的情况下使用一般的递归或许需要太多的时间与内存这时我们就可以使用记忆化搜索其本质为在递归搜索中如果遇到了没有搜索过

曾经终败给现在/ 2022年06月01日 13:49/ 0 赞/ 231 阅读

相关 HDU2571(记忆化搜索)

<table style="font-family:'Times New Roman';"> <tbody> <tr> <td align="center">

绝地灬酷狼/ 2022年05月29日 00:15/ 0 赞/ 166 阅读

相关滑雪【记忆化搜索】

滑雪 Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Mich

分手后的思念是犯贱/ 2022年05月25日 04:22/ 0 赞/ 195 阅读

相关滑雪 ————记忆化搜索

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道

￡神魔★判官ぃ/ 2022年05月17日 11:37/ 0 赞/ 152 阅读