OI题解｜LELE的RPG难题

信息奥赛题解｜LELE的RPG难题

---

🚀 题目浏览

【题目描述】

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

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

以上就是著名的RPG难题。

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

【输入】

多组数据，请处理到文件结束。

每组数据占一行，包含一个正整数 $n\ (1\le n\le 50)$.

【输出】

对于每组数据，在一行中输出一个整数，表示所有满足要求的涂法方案数。

【输入样例】

1
2

【输出样例】

3
6

【原题链接】

https://vjudge.net/problem/HDU-2045

---

☘️ 题解分析

经典题解传送门：牛客题解

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 55;
LL f[N], n;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    f[1] = 3, f[2] = 6, f[3] = 6;
    for (int i = 4; i <= 50; i++) f[i] = f[i-1] + 2 * f[i - 2];

    while (cin >> n) cout << f[n] << endl;

    return 0;
}