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;
}