http://acm.hdu.edu.cn/showproblem.php?pid=2604
题意是,有个长度为N的队列,男女一起站队,不能有男男男(fff)或者男女男(fmf)出现在对列.队列的排列方法有多少。
这个题出在这章,开始还以为是递归求解的题,就想着推公式。想了半天没有什么名目,有点急功近利,看看网上才知道可以用矩阵的解法。
现在依自己的看法分析分析这俩解法
DP解法:
当N>4时f(n)=f(n-1)+f(n-3)+f(n-4)
即最后一个字符是m时,前n-1个人的序列是F(n-1)种,最后俩是mf或者ff时,限制了倒数第三位必须是(mmf、mff),最后三个字符只有是mmf时,符合要求(没有限制),即有f(n-3)种序列,最后四个字符是mmff时符合要求(刚才的n-3的俩情况,mmf已经在n-3中体现,n-4不再考虑,只考虑mff前加个m的n-4的情况)。
总结:这个分析方式和DP的思考方式一样,站在最后的位置上,把可能会关联的前面的几个位置规划进去,从而可以推导出公式。以后做题的时候 一定要冷静,最重要的不是做出来题,而是从做题的过程中学到东西,尽量做题的时候理清思绪。
矩阵解法:
构建矩阵用快速幂取模
但是还不太理解,先放在这,待以后再更新。
据了解这个还有trie图的理解法。
假定根节点为字符串的最后一个字符,由根结点到根节点的回路有m、fmm、ffmm,注意这是从一个字符串的后面向前走这些字符到达另一个字符串,恰好和上面的扩展递推相一致。。。
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
杭州电子科技大学online judge (hdu)第十一卷 2000 - 2099 题目集 doc 格式的,希望大家喜欢!
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
解题报告|ACM|程序设计参考程序以及题目的分析
ACM程序设计题目分析以及AC的源码
最精准的答案(本人做对的题目拿上来给大家呈现)!不要忘记是C++编的
ACM题库,一些题目和答案,以及解题报告,传上来共享
我去年暑假花了5天,把杭电ACM网站上2000到2099这100道题全AC了,又花了10来天精心写解题报告。 里面包括题目、解题思路、编程技巧以及参考源码。所有代码都是使用C/C++写的。 最近整理资料时无意间发现,打包...
杭电OnlineJudge 200-2099的解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
杭电ACM2000-2099题的解题报告