荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (Aspire追月|Fight for Final), 信区: ACMICPC
标 题: 典型算法与ACM题目解析(03)—记忆化搜索的应用zz
发信站: 荔园晨风BBS站 (Wed Nov 8 15:35:26 2006), 站内
发信人: xiangsanzi (弦柱), 信区: Algorithm
标 题: 典型算法与ACM题目解析(03)—记忆化搜索的应用
发信站: 武汉白云黄鹤站 (2006年08月18日10:55:44 星期五)
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(再加上一个剪枝),而想再往上测时
经超内存了.
如果谁有更好要或者更快的方法,请发出来一起学习(组合数学的公式就算了)
--
---问天下头颅几许,且看老夫手法如何
※ 来源:·武汉白云黄鹤站 bbs.whnet.edu.cn·
--
Science is what we understand well enough to explain to a computer.
Art is everything else we do.
———— Donald E. Knuth
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.224]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店