ural 1225.Flags

1225. Flags

Time limit: 1.0 second Memory limit: 64 MB

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

ProbPlem Source:2002-2003 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 2002

题意：给出红、白、蓝三种颜色；进行涂色；

      要求一：相邻的颜色不能相同。要求二：蓝色的两侧颜色不同；

思想：递归方程：f[i]=f[i-1]+f[i-2];本来没有想到第斐波那契数列；但是通过对拍程序可以总结出来规律；

AC代码：

 

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    long long dp[50]={0};//建立辅助数组
    int n;
    cin>>n;//输入需要涂色个格数；
    int i;
    dp[1]=2;//初始化数组
    for(i=2;i<=n;i++)
    {//递推出第i格的种数；
        dp[i]=dp[i-2]+dp[i-1];
    }
    cout<<dp[n]<<endl;
    return 0;
}

对拍程序：

#include<iostream>
#include<cstdio>

using namespace std;
int main()
{
    long long dp[4][50]={0};
    int n;
    cin>>n;
    int i;
    dp[1][1]=0;
    dp[2][1]=1;
    dp[3][1]=1;
    for(i=2;i<=n;i++)
    {
        dp[1][i]=dp[2][i-1]+dp[3][i-1];
        dp[2][i]=dp[3][i-2]+dp[3][i-1];
        dp[3][i]=dp[2][i-2]+dp[2][i-1];
    }
    cout<<dp[2][n]+dp[3][n]<<endl;
    return 0;
}