计蒜课-墙壁涂色

问题

蒜头君觉得白色的墙面好单调，他决定给房间的墙面涂上颜色。他买了 3 种颜料分别是红、黄、蓝，然后把房间的墙壁竖直地划分成 n 个部分，蒜头希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。 例如，当 n = 5 时，下面就是一种合法方案。

由于墙壁是一个环形，所以下面这个方案就是不合法的。

输入格式

一个整数 n，表示房间被划分成多少部分。（1 <=n<=50）

输出格式

一个整数，表示给墙壁涂色的合法方案数。

样例输入 4 样例输出 18

思路

设ans[i]为长度为i的方案数，然后找出 ans[n] 与 ans[n - 1] 和 ans[n - 2] 的关系。 考虑第 1 块和 n-1块颜色不一样的情况，现在第 n 块要和第 n-1和 1 都不一样，但是只有 3 种颜色，所以 n 只有一种颜色选择，这种情况方案数正好是 ans[n-1]。 考虑第 1 块和 n-1 块颜色一样的情况，第 n-2 块必然要和第 n-1 块不同，同时也就和第 1 块不同，前面 n-2 块方案数是 ans[n-2]，第 n 块要和第 1 块和第 n-1块不同，有 2 种选择，所以这种情况方案数是 2∗ans[n−2]。 上面 2 种情况加起来就是总方案数。

实现代码

#include <iostream> using namespace std; int main(int argc, char *argv[]) { int n; long long ans[100]; scanf("%d",&n); ans[1]=3; ans[2]=6; ans[3]=6; if (n>=4){ for(int i=4;i<=n;i++){ ans[i]=ans[i-1]+2*ans[i-2]; } } printf("%lld",ans[n]); }