HDOJ - 2045 RPG难题

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2045

算法思想：

1）有三种颜色，在涂某一块区域时，由于它的前一块区域已经确定，且相邻区域不能重复，所以在这一块区域上有两种涂法，因此，大体意识为 a[i]=a[i-1]*2

2）（为了方便描述，我们用1，2，3分别代表R，P，G）假设第一块涂色为1，则当以第n块结尾的时候，第n块区域就不能再为1。那么，在第n块区域中一共a[n]中涂法中，有多少涂法是1呢？用递推的思想，显然，如果第n-1块涂的不是1，那么第n块区域就可以涂成1。我们用b[i]表示a[i]种涂法里被涂成1的数量，可得b[i]=a[i-1]-b[i-1]。

3）综合以上两点，我们可以得出，方格总是为n时，可以涂的方法数就是第一步计算出来的理想值减去第二步中那些和第一块相冲突的个数，即：(a[i]-b[i])*3。当然不要忘了最后的乘以3哦！

代码如下：

	a[1]=1;
	for (int i(2);i<=50;i++) a[i]=a[i-1]*2;
	b[3]=2;
	for (int i(4);i<=50;i++) b[i]=a[i-1]-b[i-1];
	for (int i(1);i<=50;i++) c[i]-=a[i]-b[i];

考虑代码优化：

仔细观察上面的方法，可以发现，其实b数组本身就是用a数组产生的，并且只是用作临时存贮。那么能不能只用一个数组来节省空间呢？

1	2	3	4	5	6	7	8 
a	1	2	4	8	16	32	64	...
b	0	0	2	2	6	10	22	42
c	1	2	2	6	10	22	42	...

通过观察，我们可以发现：

c[i]=a[i]-c[i-1]

=> a[i]=c[i]+c[i-1]

=> a[i-1]=c[i-1]+c[i-2]

又 a[i]=a[i-1]*2

整理得：c[i]=(c[i-1]+c[i-2])*2-c[i-1]

      即：c[i]=c[i-1]+c[i-2]*2

代码如下：

a[1]=1;
	a[2]=2;
	a[3]=2;
	for (int i(4);i<=50;i++) a[i]=a[i-1]+a[i-2]*2;

我的博客