Problem Description
人称 "AC 女之杀手" 的超级偶像 LELE 最近忽然玩起了深沉, 这可急坏了众多 "Cole"(LELE 的粉丝, 即 "可乐"), 经过多方打探, 某资深 Cole 终于知道了原因, 原来, LELE 最近研究起了著名的 RPG 难题:
有排成一行的n个方格, 用红 (Red), 粉(Pink), 绿(Green) 三色涂每个格子, 每格涂一色, 要求任何相邻的方格不能同色, 且首尾两格也不同色.求全部的满足要求的涂法.
以上就是著名的 RPG 难题.
如果你是 Cole, 我想你一定会想尽办法帮助 LELE 解决这个问题的; 如果不是, 看在众多漂亮的痛不欲生的 Cole 女的面子上, 你也不会袖手旁观吧?
Input
输入数据包含多个测试实例, 每个测试实例占一行, 由一个整数 N 组成,(0<n<=50).
Output
对于每个测试实例, 请输出全部的满足要求的涂法, 每个实例的输出占一行.
- Sample Input
- 1
- 2
- Sample Output
- 3
- 6
解: 首先考虑这样一个问题: 如果去掉首尾两格也不同色的条件, 那么问题就变成了有排成一行的n个方格, 用红 (Red), 粉(Pink), 绿(Green) 三色涂每个格子, 每格涂一色, 要求任何相邻的方格不能同色.
设 n 个方格以红色为结尾的种类数为 an, 以粉色为结尾的种类数为 bn, 以绿色为结尾的种类数为 cn, 如. 那么=. 也就是说 n+1 个格子的涂法 f(n+1)=an+1+bn+1+cn+1=2(an+bn+cn)=2*f(n)
那么加上首尾不相同的条件后发现状态不止有三种, 和结尾有关, 和开始有关, 结尾 3 种, 开始三种, 所以一共有九种状态, 但是这九种状态并不是都满足条件. 用式子来表达就是, 九种状态分别为
abn 表示以红色为开头, 粉色为结尾, 长度为 n 的种类数. 其他以此类推. f(n)=abn+acn+ban+bcn+can+cbn(n>1, 首尾不能相同).
, 从这个矩阵已经可以看出矩阵的三行是不相关的, 是独立的, 那么发现 abn+1+acn+1=aan+acn+aan+abn=(abn+acn)+2*aan=(abn+acn)+2*(abn-1+acn-1). 同理可得矩阵的第二行和第三行. 解得: f(n+1)=f(n)+2f(n-1).
其实这个题并不需要这么麻烦, 写这么多时感觉虽然公式不好理解, 但更容易证明他的正确性.
简单理解就是: 考虑 n 长度的时, 设 f(n)为 n 长度的种类数, 那么首先可以构造出 f(n-1)种 (因为 n-1 长度符合条件的首尾不同, 所以只能在第 n 位添加不属于前两种颜色的最后一种颜色),2*f(n-1) 种(首先给 n-1 位添加和首相同的颜色, 在第 n 位就可以有两种颜色可以添加, 就是 2*f(n-1)).
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <vector>
- #include <cmath>
- #include <queue>
- #include <deque>
- #include <cmath>
- #include <map>
- using namespace std;
- typedef long long ll;
- const double inf=1e20;
- const int maxn=2e5+10;
- const int mod=1e9+7;
- ll a[100];
- int main(){
- a[0]=3;
- a[1]=a[2]=6;
- for(int i=3;i<60;i++){
- a[i]=a[i-1]+2*a[i-2];
- }
- int n;
- while(scanf("%d",&n)!=EOF){
- printf("%lld\n",a[n-1]);
- }
- return 0;
- }
hdu 2045 不容易系列之(3)-- LELE 的 RPG 难题
来源: http://www.bubuko.com/infodetail-3453525.html