种树
种树
http://www.nowcoder.com/questionTerminal/52f25c8a8d414f8f8fe46d4e62ef732c
题解:
题目难度:三星
考察点: 深度优先搜索,回溯,剪枝
易错点:
这个题目对于同学们来说做法非常直接,就是递归+回溯,也很容易想。但是因为物品的数量达到了,如果用简单的不进行剪枝的话,是无法跑过所有数据的,因此需要做一些剪枝。
题解:深度优先搜索+剪枝
这个题目的做法很显然,就是使用递归+回溯,每次从编号枚举物品,如果当前物品的数量不为,且已经排好了的上一个和当前物品不同,则可以把当前物品加入序列,然后不断递归下去,直至所有的物品都被取完。然后这里存在一个可以剪枝的地方,如果当前序列中数量最多的物品都数量的倍,大于剩余物品数量加,则说明当前的摆放方式是不合法的,可以直接剪掉。因为这种情况下,不可能让两个相邻的物品都不是同一种。加上这个剪枝,也就能轻松这道题目了。
#include "bits/stdc++.h" using namespace std; const int maxn=2000+10; int n,a[maxn],b[maxn]; int check(){ int pos=-1,mx=0; for(int i=1;i<=n;i++){ if(a[i]>mx){ mx=a[i]; pos=i; } } return pos; } bool dfs(int cur,int m){ int pos=check(); if(pos==-1) return true; if(a[pos]*2>m+1) return false; for(int i=1;i<=n;i++){ if(a[i]&&b[cur-1]!=i){ a[i]--; m--; b[cur]=i; if(dfs(cur+1,m)) return true; a[i]++; m++; b[cur]=0; } } } int main() { scanf("%d",&n); int m=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); m+=a[i]; } if(dfs(1,m)){ for(int i=1;i<=m;i++) printf("%d ",b[i]); printf("\n"); }else{ printf("-\n"); } return 0; }