RGB项链问题

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4369

Description

人称AC之神的QIGe最近一直忙着培养NOI高手,为了鼓励NOI高手, QiGe做了若干雨花石项链,作为对表现优秀的选手的奖励.他会挑选一个雨花石作为这串项链的开始,然后一个接一个连起来,现在他有三种颜色的雨花石,红(Red)、绿(Green)、蓝（Blue),做项链的时候他要求每相邻的2个雨花石不能相同的颜色，尽管最后一步把首尾连接起来的工作QiGe不需要去做，但也必须保证首尾2个雨花石它们是不同颜色。你知道QiGe有多少种串项链的方法吗？

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。

Output

对于每个测试实例，请输出全部的满足要求的排法，每个实例的输出占一行。

Sample Input

1 2

Sample Output

3 6 #include <bits/stdc++.h> using namespace std; long long a[100]; //涂三色 相邻和收尾不得相同色； // 思路： 前四个会因为数量不受大规律 // n>=4时，第n-1个与第一个不相同时，则为f（-1） 相同时 ：则第n个有两种不同于第一个的可能此时为f（n-2）2 故的规律 int main() {int n,i,j;a[1]=3;a[2]=6;a[3]=6;a[4]=18;for(i=5;i<=51;i++){a[i]=a[i-1]+2*a[i-2];}while(scanf("%d",&n)!=EOF){printf("%lld\n",a[n]);} return 0; }

进阶版

RGBP

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4375

Description

人称AC之神的QIGe最近一直忙着培养NOI高手,为了鼓励NOI高手, QiGe做了若干雨花石项链,作为对表现优秀的选手的奖励.他会挑选一个雨花石作为这串项链的开始,然后一个接一个连起来,现在他有四种颜色的雨花石,红(Red)、绿(Green)、蓝（Blue)、紫色（Pink）,做项链的时候他要求每相邻的2个雨花石不能相同的颜色，尽管最后一步把首尾连接起来的工作QiGe不需要去做，但也必须保证它们是不同颜色。你知道QiGe有多少种串项链的方法吗？

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0 < n <= 30)。

Output

对于每个测试实例，请输出全部的满足要求的排法，每个实例的输出占一行。

Sample Input

1 2

Sample Output

4 12

HINT

 

Source

爆搜找规律

#include <bits/stdc++.h> using namespace std;long long a[1007],b[1008]; long long ans=0; void bfs(int k,int c){if(k==c+1){if(b[1]!=b[c]||c==1)ans++;return;}for(int i=1;i<=4;i++){if(k==1||b[k-1]!=i){b[k]=i;bfs(k+1,c); }}}int main() {for(int i=1;i<=31;i++){ans=0;bfs(1,i);printf("%d %lld\n",i , ans);} return 0; }

得到规律f【n】=2*f【n-1】+3*f【n-2】

#include <bits/stdc++.h> using namespace std;long long a[1007],b[1008]; int main() {int n,i,j;a[1]=4;a[2]=12;a[3]=24;a[4]=84;a[5]=240;for(i=6;i<=39;i++){a[i]=2*a[i-1]+3*a[i-2];} while(scanf("%d",&n)!=EOF){printf("%lld\n",a[n]);}return 0; }

 

总结

以上是生活随笔为你收集整理的RGB项链问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。