UVa 10254

四柱汉诺塔

首先找出状态转移方程
f(x) = min{ f(i)*2 + 2^(x-i)-1 | 0<=i<x }

由于N最大能到10000,
所以不仅要使用大数，直接DP也是过不了的。

为了让复杂度降低，需要找一下规律。

打印出公式中所有取到最值的i（命该值为y），发现y要嘛是不变的要嘛是递增的。
所以每次计算的时候，只要取上一次的y，和y+1比较即可。
时间复杂度便降低到了O(N)

看题解有人找出规律，在这里也顺便说一下： f(1)=1，之后每i个数增加2^(i-1)，i为大于等于2的自然数列，用大数处理即可