荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: 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软件 网络书店