HDU 2045 不容易系列之(3)—— LELE的RPG难题 （递推）

题意：略。

析：首先是假设前n-2个已经放好了，那么放第 n 个时，先考虑一下第 n-1 放的是什么，那么有两种情况。

如果n-1放的是和第1个一样的，那么第 n 个就可以在n-2的基础上放2个，也就是2 * f(n-2),也就是说，因为第n-1和第1个一样，

所以第 n 个有两种（不和第1个样的其他种）。那么如果第n-1个放的不和第1个一样呢？那么第 n 个就和第 n-1 个一样，没有选择，只能放一个。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f3f;

const double eps = 1e-8;

const int maxn = 1e4 + 5;

const int mod = 1e9 + 7;

const int dr[] = {0, 0, -1, 1};

const int dc[] = {-1, 1, 0, 0};

int n, m;

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

LL ans[55];

void init(){

    ans[1] = 3;

    ans[2] = ans[3] = 6;

    for(int i = 4; i <= 50; ++i)

        ans[i] = ans[i-1] + ans[i-2] * 2LL;

}

LL f(int n){

    if(1 == n)  return 3;

    if(2 == n || 3 == n)  return 6;

    return f(n-1) + f(n-2) * 2LL;

}

int main(){

    int n;

    init();

  //  while(cin >> n)  cout << f(n) << endl;

    while(cin >> n)  cout << ans[n] << endl;

    return 0;

}