「日常训练」 不容易系列之(3)—— LELE的RPG难题 （HDU 2045）

题目简述

有排成一行的n" role="presentation">nn个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色，求全部的满足要求的涂法。

分析

首先感谢题解，我个人想半天是出不来的。

考虑第n个与第n-1个的关系。因为第n个不能和第1个同色，那么第n个颜色就是我们判断的突破口，而它是由第n-1个决定的。如果第n-1个保持原来的状况不变，那么第n个只能有一种可能，整个情况数就是原来的fn−1" role="presentation">fn−1fn−1；如果第n-1个不保持原来的情况（那么就只会是一种颜色——和第一个一样），那么相当于n-2是最后一个。这样一来，最后一色有两种情况，这种大情况的整个数目就是2fn−2" role="presentation">2fn−22fn−2。边界条件处理好即可。

这种递推题完成后，一定要代入最大值要看是否越界！！！

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#define inf 0x3f3f3f3f

#define PB push_back

#define MP make_pair

#define fi first

#define se second

#define lowbit(x) (x&(-x))

#define rep(i, a, b) for(int i = (a); i <= (b); i++)

#define per(i, a, b) for(int i = (a); i >= (b); i--)

#define pr(x) cout << #x << " = " << x << " ";

#define prl(x) cout << #x << " = " << x << endl;

#define ZERO(X) memset((X),0,sizeof(X))

#define ALL(X) (X).begin(),(X).end()

#define SZ(x) (int)x.size()

using namespace std;

typedef pair<int, int> PI;

typedef pair<pair<int, int>, int> PII;

typedef pair<pair<pair<int, int>, int>, int> PIII;

using ull= unsigned long long;

using ll = long long;

using ld = long double;

#define quickio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

/*      debug("Precalc: %.3f\n", (double)(clock()) / CLOCKS_PER_SEC);

clock_t z = clock();

        solve();

        //debug("Test: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);

*/

template<typename T = int>

inline T read() {

    T val=0, sign=1;

    char ch;

    for (ch=getchar();ch<'0'||ch>'9';ch=getchar())

        if (ch=='-') sign=-1;

    for (;ch>='0'&&ch<='9';ch=getchar())

        val=val*10+ch-'0';

    return sign*val;

}

int main()

{

    ll arr[55]={0,3,6,6};

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

        arr[i]=arr[i-1]+2*arr[i-2];

    int n;

    while(cin>>n)

    {

        cout<<arr[n]<<endl;

    }

    return 0;

}