用矩阵求解递推式第n项(n非常大)

Problem A

Time Limit : 15000/5000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 36   Accepted Submission(s) : 11

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

Chef Ciel lives in a long street which can be thought as of x-axis of coordinate system. Her house is at coordinate 0 whereas her restaurant is situated at coordinate N. Usually Ciel goes from home to restaurant taking a step of size 1 or 2 in forward direction. We all know how much Chef loves Fibonacci numbers.
But today, Ciel being little casual stepped in wrong direction on her way to her restaurant exactly once and of course she did not set her foot wrong at home. Now she wonders how many ways she can reach her restaurant provided that she stepped wrong once but not at home.
She does not go past her restaurant because it is altogether different world and once she reaches her restaurant she stops.

hdoj1207

T(n)=min(2*T(k)+pow(2,n-k)-1) (1<=k && k<=n-1)
设杆子为ABCD,要把盘子从A移到C,那么移动次数为
先把k个盘子从A经B、C移到D(移动次数为T(k))
然后把n-k个盘子从A经B移到C(也就是普通的三根柱子的情况,移动次数为pow(2,n-k)-1)
之后再把k个盘子从D经A、B移到C(移动次数为T(k))
可见本题是动态规划题,状态转移方程为:
T(n)=min(2*T(k)+pow(2,n-k)-1) (1<=k && k<=n-1)

hdoj1997

递归真是好东西,就是想不到,下面是网上的摘录过来的思路:
1) 最初我们要判断一下是不是已经完全放好了,这样就不用考虑是不是最优化了, 因为都已经放好了,肯定是最合法的! 或者说全部在A上,这是还没开始动作的一个状态,所以也是合法的!
2) 否则我们 要对每次状态的最大的那个进行判断,因为我们知道,汉诺塔最大的那个不可能停在B上,(假设 最初的时候都在A上,要移到C上去!),只可能在A或者C上面!如果是放在B上面,停止判断,直接断定他非法~这样我们得出了第二个判段依据!
3)如果最大的在A上面,我可以想到的是,他还没有放在C上,此时这个状态的上面一系列状态都是想把其他的放在B上,然后就可以把A放到C上了,所以我们在这里做出更新,因为他上面一系列动作都是想让A上面的除最大的外都放到B上面去,所以,我们这个时候往上考虑,对N-1进行 判断!这个时候动作的方向是A->B所以为了统一操作,我们得把B跟C互换!
4)如果最大的在C上面,这时候倒数第二大的不是放在B上就是C上,我们要把要把倒数第二大的以及其他的放在C上,这时候的动作方向是B—>C;所以把A跟B交换一下!

hdoj1143

难度值为1的一道题,可是,,,想了好久。。不过还是想出来了
思路:叙述起来比较困难(主要是不知道怎么作图。。),好吧,只给出我推出来的递推式:
f[0]=1
f[n]=f[n-2]+2*(f[n-2]+f[n-4]+……+f[0]]) n>=2
提示:考虑最后3*2方格,还有一种不能只考虑最后3*2方格的情况
(这题最奇怪的是,我认为f[0]=0,但是题目人为的是f[0]=1。。)