URAL 1225. Flags

Author: 2015-09-14

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1225

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. For N = 3 result is following:
Problem illustration

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
Problem Source: 2002-2003 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 2002

2. 思路

用红、白、蓝三种颜色的彩条制作旗子，要求相邻两个彩条颜色不同，蓝条必须放置在红条和白条之间，给出彩条数量n，求有多少种符合要求的旗子。

动态规划。使用cnt[i]表示使用i个彩条的旗子数量：

  • i = 1时，旗子只有一个彩条，只能使用红色或白色，cnt[1] = 2；
  • i = 2时，旗子有两个彩条，只能使用红色+白色，或者白色+红色，cnt[2] = 2；
  • i >= 3时：
    • 首先考虑在cnt[i – 1]的基础上追加一个彩条所能形成的旗子数量。cnt[i – 1]表示使用i – 1个彩条所能形成的旗子数量，这些旗子中，最后一个彩条（第i – 1个彩条）只能是红色或白色：如果第i – 1个彩条是红色，则追加白色彩条；如果第i – 1个彩条是白色，则追加红色彩条。这样就有了cnt[i – 1]种使用i个彩条的旗子。
    • 然后考虑在cnt[i – 2]的基础上追加两个彩条所能形成的旗子数量。cnt[i – 2]表示使用i – 2个彩条所能形成的旗子数量，这些旗子中，最后一个彩条（第i – 2个彩条）只能是红色或白色：如果第i – 2个彩条是红色，追加蓝+白两个彩条；如果第i – 2个彩条是白色，则追加蓝+红的两个彩条。这样就有了cnt[i – 2]种使用i个彩条的旗子。追加白+白、红+红违反题目条件，追加白+红、红+白与上面重复。

综上，有：

cnt[1] = 2,
cnt[2] = 2,
cnt[i] = cnt[i - 1] + cnt[i - 2], i >= 3.

3. 代码

注意这里使用了long long int来计数，否则会溢出。

#include <cstdio>

const int MAX_N = 46;

void solveE6e_Flags();

int main() {
    solveE6e_Flags();
}

long long int cnt[MAX_N];
void solveE6e_Flags() {
    int n;
    scanf("%d", &n);
    
    cnt[1] = cnt[2] = 2;
    for (int i = 3; i <= n; ++i)
    cnt[i] = cnt[i - 1] + cnt[i - 2];
    
    printf("%lld\n", cnt[n]);
}