Timus 1225. Flags Fibonacci的应用

On the Day of the Flag of Russia a shop-owner decided to decorate the show-window of his shop with textile stripes of white, blue and red colors. He wants to satisfy the following conditions:

1. Stripes of the same color cannot be placed next to each other.
2. A blue stripe must always be placed between a white and a red or between a red and a white one.

Determine the number of the ways to fulfill his wish.

Example.ForN= 3 result is following:

Input

N, the number of the stripes, 1 ≤N≤ 45.

Output

M, the number of the ways to decorate the shop-window.

Sample

input output

3	4

原来Fibonacci可以这么来使用的，本题的动态规划法应用，大略分析如下：

f(n) = f(n-1) + f(n-2)

when f(n-1)put W and [R,...(n-1)] or R and [W,...(n-1)]

when f(n-2)put R,B and [W,..(n-2)] or W,B and [R,...(n-2)]

Why OR? Because if we do both, then we get repeated flags, so it make a finonacci sequence.

class Flags1225
{
	static const int N = 46;
	long long A[N];
public:
	Flags1225()
	{
		A[0] = 0, A[1] = 2, A[2] = 2, A[3] = 4;
		for (int i = 4; i < N; i++)
		{
			A[i] = A[i-1] + A[i-2];
		}
	}
	void run()
	{
		int a = 0;
		cin>>a;
		cout<<A[a];
	}
};