PAT 解题报告 (Basic Level) 1005. 继续(3n+1)猜想 (25)

题目描述:

具体题目见: http://pat.zju.edu.cn/contests/pat-b-practise/1005

算法分析:

这个题目就是稍微转了转弯, 真的实现的代码和1001那题没任何差别。其实题目描述中也已经有了提示,就是要记忆中间结果(DP思想)。我们的关键观察就是: 如果一个数字已经被“覆盖”了, 那么被这个数字“覆盖”的所有数字就一定也已经被检查过了,没必要再重复计算去test那些剩下的数字。 有了这一个我们看一个具体的例子:

6
3 5 6 7 8 11

算法的具体执行过程如下:遍历这一排数字,所有数字的初始状态都是没有被“覆盖”到,第一个是3, 首先检查3有没有被“覆盖”, 没有(因为初始状态是没有被“覆盖”), 那么求得3能够“覆盖”的数字, 3->5->8->4->2->1,我们标记5,8,4,2,1都已经被“覆盖”, 好了到第二个数字5我们先检查5是否已经被“覆盖”, 5已经被“覆盖”了,那么我们直接跳过, 这里注意我们能直接跳过的原因是因为我们没必要再去检查5能够“覆盖”哪些数字,因为既然5自己都已经被“覆盖”了,势必在前面的某一次检查中已经完成了5所能“覆盖”那些数字的检查。 同样道理我们继续,看6,6没有被“覆盖”,那么我们检查6可以cover哪些数字: 6->3->5….好了这里其实到5我们就可以停止检查了,因为5的状态是已经被“覆盖”,同样的原因我们没必要继续下去。以此类推,我们只需要一次扫描就能知道这一列数(3 5 6 7 8 11)哪些数字被“覆盖”哪些没有,最后扫描一次,输出那些没有被cover的(降序)。

注意点:

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on March 28, 2013