通常称交通灯为红绿灯，其实是不准确的，一般信号灯有Red、Green和Yellow三种颜色。
现在有一个巨型的交通灯，一排共N个灯，它们都可以发出有红、绿、黄三种灯光。为了显目，规定：（1）不得有灭的灯；（2）相同颜色的灯相邻不得超过3个。
请你计算有多少种可靠的信号灯排列方案？
一行，一个整数N（3＜N＜20）。
一行，一个整数M，可行的方案数。
4
78
我们设$a[i]$为第$i$个灯与第$i-1$个灯颜色不同的方案数。
此时易得递推公式$a[i]=a[i-1]\times2+a[i-2]\times2+a[i-3]\times2$。
根据定义的最终答案为$a[n]+a[n-1]+a[n-2]$。
#include <iostream> using namespace std; int n; int a[20] = {0,3,6,18}; int main() { cin >> n; for(int i = 4; i <= n; i++) { a[i] = a[i - 1] * 2 + a[i - 2] * 2 + a[i - 3] * 2; } cout << a[n] + a[n - 1] + a[n - 2]; return 0; }
原文：https://www.cnblogs.com/kcn999/p/10659530.html
