首页 > ACM题库 > HDU-杭电 > hdu 2045 不容易系列之(3)―― LELE的RPG难题-动态规划-[解题报告]C++
2013
12-26

hdu 2045 不容易系列之(3)―― LELE的RPG难题-动态规划-[解题报告]C++

不容易系列之(3)―― LELE的RPG难题

问题描述 :

人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即"可乐"),经过多方打探,某资深Cole终于知道了原因,原来,LELE最近研究起了著名的RPG难题:

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

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

输入:

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

输出:

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

样例输入:

1
2

样例输出:

3
6

初级DP。

网上还有更精简的代码,只用一维数组。 参考:http://hi.baidu.com/zihuacs/item/cd160b84ef1c782d100ef3ad

#include "stdio.h"
#include "string.h"
void main(){
	int n, i;
	__int64 dp[51][3][3];  //分别表示:第i个方块 3种颜色 序列的第一个方块的颜色

	freopen("in.txt", "r", stdin);

	while(scanf("%d", &n)!=EOF){
		memset(dp, 0, sizeof(dp));
		dp[1][0][0] = 1;
		dp[1][1][1] = 1;
		dp[1][2][2] = 1;
		for(i=2; i<=n; i++){
			dp[i][0][0] = dp[i-1][1][0] + dp[i-1][2][0];  //第i个方块的第0种颜色且起始方块颜色为0的个数,等于第i-1个方块的第1种……
			dp[i][0][1] = dp[i-1][1][1] + dp[i-1][2][1];
			dp[i][0][2] = dp[i-1][1][2] + dp[i-1][2][2];
			
			dp[i][1][0] = dp[i-1][0][0] + dp[i-1][2][0];
			dp[i][1][1] = dp[i-1][0][1] + dp[i-1][2][1];
			dp[i][1][2] = dp[i-1][0][2] + dp[i-1][2][2];
			
			dp[i][2][0] = dp[i-1][0][0] + dp[i-1][1][0];
			dp[i][2][1] = dp[i-1][0][1] + dp[i-1][1][1];
			dp[i][2][2] = dp[i-1][0][2] + dp[i-1][1][2];
		}
		if(n==1)
			printf("3\n");
		else
			printf("%I64d\n", dp[n][0][1]+dp[n][0][2] + dp[n][1][0]+dp[n][1][2] + dp[n][2][0]+dp[n][2][1]);
	}
}

解题转自:http://blog.csdn.net/chaoojie/article/details/7714126


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?