递推 hdu 2064

z[n] n个盘子从1到3次数

先想2个的时候  1->2 2->3  1->2 3->2 2->1 2->3 1->2 2->3

显然 要先把上面n-1 先移动到3  然后 1->2  然后 3->1 然后 2->3 然后 1->3

其实就是 在z[n]=3*z[n-1]+2;

如果整理一下 就可以o(1);

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

using namespace std;

typedef long long ll;

#define MAXN 105

ll z[MAXN];

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        ll ans=;

        for(int i=;i<=n;i++)

            ans*=;

        printf("%lld\n",ans-);

    }

    return ;

}