Problem Description
不知道大家有没有玩过一个叫做 九连环 的玩具,如下图所示。
如果你不了解九连环,那玄黄就带你领略九连环的奥妙:
九连环是我国传统的民间智力玩具,玩具上面有九个连环套在杆上,目标就是通过一定的方式将九个连环从杆上全部取下来。 玩法是这样的: 1、对每个环,有2种操作:把这个环放到杆上或把这个环从杆上取下 2、你可以随意的对第1个环进行操作 3、如果你想对第i个环(i>1)进行操作,你必须将第i-1个环放在杆上,且必须把前i-2个环从杆上取下Input
输入一个整数n ( 0<n<10 ),代表杆上面的连环个数。
Output
输出把所有连环取下来的最少操作步骤,每一步占一行,输出一个整数i和操作”UP”或者”DOWN”,代表将第i个环放到杆上或从杆上取下来,整数和操作用空格分开。详情见示例输出。
首先我们一定是想先把最后面的拿掉
1.每次拿掉第i个位置时要先看i-1的位置是否存在;
2.存在,需要把i-1之前的拿掉 此时i = i - 2
3.不存在 需要将i-1的位置变为存在 此时i = i - 1
#includeusing namespace std;#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define ls now<<1#define rs now<<1|1#define lson l,mid,ls#define rson mid+1,r,rs#define inf 0x3f3f3f3fint arr[15];string a="DOWN",b="UP";void dfs(int n){ if(n<1) return ; for(int i=n;i>=1;i--) { if(arr[i-1]) dfs(i-2); if(arr[n-1]==0) dfs(i-1); } cout< <<" "<<(arr[n]?a:b)< >n; dfs(n); return 0;}