zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

搜索+剪枝

详见注释

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define rg register
#define Fur(i,x,y) for(int i=x;i<=y;++i)
#define Fdr(i,x,y) for(int i=x;i>=y;--i)
#define fin(s) freopen(s".in","r",stdin)
#define fcin ios::sync_with_stdio(false)
using namespace std;
#define N 70
int n,a[N],nxt[N],len,s=0,tot;
bool cmp(int x,int y){return x>y;}
bool v[N];
void dfs(int res,int d,int la){ // 当前木棍剩下多少没拼,第几根木棍,上一次用的最后一根的位置
    if(!res){
        if(d==tot){
            cout<<len<<endl;
            exit(0);
        }
        Fur(i,1,n)if(!v[i]){
            v[i]=1;
            dfs(len-a[i],d+1,i);
            v[i]=0;
            break;
        }
    }
    Fur(i,la+1,n)if(!v[i]&&res>=a[i]){
        v[i]=1;
        dfs(res-a[i],d,i);
        v[i]=0;
        if(res==a[i]||res==len)return;// a[i]用在当前木棍不合适
        i=nxt[i];
        if(i==n)return;
    }
}
int main(){
    fin("in");
    fcin;
    cin>>n;
    Fur(i,1,n){
        cin>>a[i];
        if(a[i]>50)--i,--n;
    }
    Fur(i,1,n)s+=a[i];
    sort(a+1,a+n+1,cmp);//排序 从大到小放

    nxt[n]=n;
    Fdr(i,n-1,1)
        if(a[i]==a[i+1])nxt[i]=nxt[i+1];
        else nxt[i]=i;
    // 预处理出最后一个与他相同的数

    for(len=a[1];len*2<=s;++len)
    if(s%len==0){// 判断是否符合条件
        tot=s/len;
        v[1]=1;
        dfs(len-a[1],1,1);
        v[1]=0;
    }
    cout<<s<<endl;
}
LG 1120 小木棍 [数据加强版]
comment评论
Search
search