种树

种树

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;
}
全部评论

相关推荐

点赞 评论 收藏
分享
点赞 1 评论
分享
牛客网
牛客企业服务