HDU (2045 不容易系列之(3)—— LELE的RPG难题)

spoiler posted @ 2011年4月24日 22:55 in 规律及递归经典题 , 1320 阅读

题目大意:有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法.

题目分析:

这个题目刚刚开始,规律是找出来了,但是边界木有考虑好啊!

首先来分析一下:

假设求N个格子有多少种图法:

1)当N-1个与第一个相同颜色,所以这种图法不合法,从而映射出,第N-2个肯定合法!所以这时候我们有两种图法,即不用考虑第N-1个,只用考虑N-2合法的染法种类数  : 2*F[ N-2];

2) 当N-1个与第一个不相同,说明从第一个到第N-1个都是合法的图法,我们就不用考虑太多,这里只能用一种颜色了,您想啊,头用了一种颜色,N-1用了一种颜色,第N个既不能与第一个相同,又不能与第N-1个相同,那么只有一种颜色了,这时候只用考虑N-1的长度的合法种类: F[ n-1]

F[ N ] = F[ N-1 ]+2* F [ N-2 ];

但是这里要考虑边界问题!

f[1]=3;

f[2]=6;

f[3]=6;

这里的三个格子比较特殊,因为总公才3种颜色,相邻,头尾颜色各异,所以个数为2的 与格子数为3的 图法一样

代码:

#include<iostream>
#include<cstdio>
using namespace std;
double s[55]={0};
int main(){
	int i,n;
	s[1]=3;
	s[2]=6;
	s[3]=6;
	for(i=4;i<=50;i++)
		s[i]=s[i-2]*2+s[i-1];
	while(scanf("%d",&n)!=EOF){
		printf("%.0lf\n",s[n]);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter