【bzoj1019】汉诺塔
题意
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1019
分析
思路1：待定系数+解方程
设\(f[n]\)为\(n\)个盘子的答案。
看似这么简单的设数方式！
我们大胆地猜想，它存在线性的递推式！
不难想到先模拟出前几项，然而用待定系数+解方程解出递推式（然而我最初并没有想到...），然后直接递推就OK了。
%%WJMZBMR
思路2：递推
设\(f[x][i]\)表示第\(x\)根柱子上有\(i\)个盘子的最少转移次数，以及转移到的柱子为\(g[x][i]\)
奠基：
\(f[x][1]\)根据优先级来求
\(g[x][1]=1\)
转移：当前已知\(f[?][i-1]\)和\(g[?][i-1]\)的答案，考虑求解\(f[x][i]\)和\(g[x][i]\)
设\(y=g[x][i-1],k=(1+2+3)-(x+y)\)，即没有用的哪根柱子。第一步必然是将\(x\)的\(i-1\)个移到\(y\)，接下来需要分类讨论。
①当\(g[y][i-1]=k\)时，我们选择这样的策略：
- 将\(x\)的\(i-1\)个移到\(y\)
- 将\(x\)的最后一个移到\(k\)
- 将\(y\)的\(i-1\)个移到\(k\)
得到：
\(f[x][i]=f[x][i-1]+1+f[y][i-1]\)
\(g[x][i]=k\)
②当\(g[y][i-1]=x\)时，我们选择这样的策略：
- 将\(x\)的\(i-1\)个移到\(y\)
- 将\(x\)的最后一个移到\(k\)
- 将\(y\)的\(i-1\)个移到\(x\)
- 将\(k\)的唯一一个移到\(y\)
- 将\(x\)的\(i-1\)个移到\(y\)
得到：
\(f[x][i]=f[x][i-1]+1+f[y][i-1]+1+f[x][i-1]\)
\(g[x][i]=y\)
为什么这样是正确的？
其实并不知道......
但好像汉诺塔一类的问题都是这样贪心就可以了。
小结
（1）汉诺塔一类的问题
知结论。
会递推。
会递归。
（2）一类待定系数法解决的问题
对于求\(f(n)\)这类的问题，我们可以大胆地猜想：它是线性的。
然后求解前几项，再解出来，然后就很容易了，最多结合个什么矩阵乘法之类的。
有时候不是线性的也可以解决啊。
例如\(f[i]=af[i-1]^2+bf[i-1]+c\)，依然可以使用待定系数求解。
类似的问题：bzoj1002轮状病毒