VJ水题堆：hdu 2045 不容易系列之(3)―― LELE的RPG难题

2019-11-11 05:31:51

字体：大中小

来源：转载

供稿：网友

好吧，这又是VJ水题堆里的一道题。纠结了好长时间，终于把这道题磕过了，用到了很简单的深搜和记忆化搜索。不过上网搜代码的时候发现只是一道简单的数学题 /想哭.jpg 先掏出小本本记录下把这道题作为数学题的解题方法

首先 f(1)=3;f(2)=6;f(3)=6 现在考虑n>3的情况，若第n-1个格子和第一个格子不同，则为f(n-1)；若第n-1个格子和第1个格子相同，则第n-2个格子和第一个格子必然不同，此时为f(n-2)再乘第n个格子的颜色数，很显然第n个格子可以是第一个格子（也是第n-1个格子）的颜色外的另外两种，这样为2*f(n-2)；

因此总的情况为f(n)=f(n-1)+2*f(n-2);

哎呀这解题方式真是妙啊，一下就否定了我一下午的辛勤劳作，还挺让我不甘心的。不过我自己是用深搜做的，这是我的博客，所以一定要炫耀一下我第一次独立写的深度搜索。

#include<stdio.h>#include<string.h>int color[100],Ncolor;int num;int ways;//红色为1，绿色为2，蓝色为3#define Q(x){/ num=x;ways=0;/ memset(color,0,sizeof(color));Ncolor=0;/ dfs(0);PRintf("%d/n",ways);}/*RPG思路：当前的颜色块不能与上一块相同。最后一块颜色块（n>=2）不能与第一块相同可以设上一块颜色为Ncolor，作为全局变量储存当输入数据为n时：Q(n)代表总共有n块需要涂色，0种方法，将色块清空。此时对于第一块来说不能涂的颜色是0从0开始进行涂色试探试探过程：先涂color[0]块，给它涂1，2，3三种颜色；如果当前色块是可以涂色的(color[cur]!=Ncolor)，就将不能涂的颜色改为当前颜色，并进行下一块颜色的试探；如果该涂第i块时，发现i==n，说明已经完全涂完了一次。这个时候需要检验刚刚涂的那一块（也就是最后一块）的颜色是否跟第一次一样。如果n==1，方法数++；如果n>1且color[0]!=color[n-1]，方法数++;如果n>1且相等，直接return；*/void dfs(int cur){ if(cur==num) { if(num==1){ways++;return;} if(color[cur-1]!=color[0]) ways++; return; } for(int i=1;i<=3;i++) { color[cur]=i; if(color[cur]!=Ncolor) { int t=Ncolor; Ncolor=i;dfs(cur+1); Ncolor=t; } }}int main(){ int x; while(scanf("%d",&x)!=EOF) { Q(x); } return 0;}

好，这就是深度搜索TLE的失败案例。因为彻底没有找到一个递推关系式，所以也没有成功做到记忆化搜索。也就是说，下午的时间我只是自己熟悉了一下深搜。开心！！！！！

上一篇：第四章-简单绘图

下一篇：《剑指offer》 NO.8 跳台阶