牛客在线编程_种树

题目地址
给n种树一共m棵，要求构造出相邻两棵树不同种的最小字典序的方案。

• 搜索，然后如果出现某种树的数量超过还没放的位置数的一半就剪枝。

code

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+50;
int n,m,c[N];
bool flag;
vector<int> ans;
void dfs(int idx){
    if(idx==m){
        flag=true;
        return;
    }
    //剪枝
    for(int i=1;i<=n;i++){
        if(c[i]>(m-idx+1)/2){
            return;
        }
    }
    for(int i=1;i<=n;i++){
        if(c[i] && (idx==0 || ans[idx-1]!=i)){
            c[i]--;
            ans.push_back(i);
            dfs(idx+1);
            if(flag){
                return;
            }
            ans.pop_back();
            c[i]++;
        }
    }
}
int main(){
//    freopen("in.txt","r",stdin);
    scanf("%d",&n);
    int mx=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
        m+=c[i];
        mx=max(mx,c[i]);
    }
    if((m%2 && mx>(m-mx+1)) ||(m%2==0 && mx>(m-mx))){
        printf("-
");
        return 0;
    }
    //construct
    flag=false;
    dfs(0);
    if(flag){
        for(int i=0;i<m;i++){
            printf("%d%c",ans[i],i==m-1?'
':' ');
        }
    }else{
        printf("-
");
    }
    return 0;
}