A - 不容易系列之(3)―― LELE的RPG难题简单递推

人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE的粉丝,即"可乐"）,经过多方打探，某资深Cole终于知道了原因，原来，LELE最近研究起了著名的RPG难题:

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

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

Input输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。
Output对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。
Sample Input

1

2

Sample Output

3

6

要求有两个：
1.相邻元素不能同色
2.首尾元素不能同色
由要求可知，首尾的元素比较特殊要求满足两个规则，那么对最后一位元素，要求它既和首元素不同，又和第n-1个元素不同 （假设元素共有n个）
显然要分析第n-1个元素和第一个元素的关系：
如果两个同色，那么尾部元素可能取两种与该颜色不同的颜色，同时尾部两个元素去除不考虑，前面仍然是满足要求的序列（第n-2和n-1不相同，而n-1和第一个相同，可推出第n-2和第1个不相同）
满足要求，数量是 2*a[n-2]
如果两个不同颜色，那么尾部元素只能取一种，由于第1和第n-1不同颜色，所以不考虑最后一位情况下有a[n-1]个情况
可以推出关系式 a[n] = a[n-1] + 2*a[n-2] //a[i]表示长度为i的解的个数

#include <iostream>

#include <vector>

#include <algorithm>

#include<string>

#include<cstdio>

#include<cstring>

using namespace std;

/*

0 1 2 表示三种颜色

递归填色

*/

typedef long long LL;

#define MAXN 55

LL a[MAXN];

void init()

{

    a[] = ;

    a[] = ;

    a[] = ;

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

        a[i] = a[i-] + *a[i-];

}

int main()

{

    init();

    int n;

    while(cin>>n)

        cout<<a[n]<<endl;

    return ;

}

巴特西

A - 不容易系列之(3)―― LELE的RPG难题简单递推

最新文章

热门文章

巴特西

A - 不容易系列之(3)―― LELE的RPG难题 简单递推

最新文章

热门文章

A - 不容易系列之(3)―― LELE的RPG难题简单递推