Luogu P1120 小木棍［数据加强版］来来来我们一起来剪枝，剪枝，剪枝、、、...

矫情吗；* 2021-11-17 15:26 392阅读 0赞

好啊。。。太棒了。。。

--------------------

dfs（拼到第几根木棍，这根木棍剩余长度，上一根木棍的位置）

len是木棍的长度，cnt是木棍的个数

震撼人心的剪枝：

1.枚举长度从最大的木棍开始，直到sum/2,因为之后只能是一整个了。。

2.木棍从大往小试，减少状态数；

3.等长木棍搜索后，就跳过另一根等长的，因为状态实际上一样

4.从比上一根长度更短的开始枚举，避免重复状态

5.二分合法长度而不是一个个枚举(实测会快一些)

6.一旦成立就直接return

7.如果 a\[i\] 不能形成一个可行方案，且 剩余长度==a\[i\]或==len 代表后面更短的小木棍也拼不成整根木棍，直接 return

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #define R register int
    using namespace std;
    inline int g() {
        R ret=0; register char ch; while(!isdigit(ch=getchar())) ;
        do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret;
    }
    int n,len,sum,cnt;
    int a[70];
    bool v[70],flg;
    inline int _upper_bound(int l,int r,const int& dst) 
    　　{
        while(l<r) {R md=l+r>>1; if(a[md]<=dst) r=md; else l=md+1;} return l;}
    void dfs(int stk,int res,int lst) { 
        if(!res) { if(stk==cnt) {flg=true; return ;} R i;
            for(i=1;i<=n;++i) if(!v[i]) break;
            v[i]=true; dfs(stk+1,len-a[i],i); v[i]=false; if(flg) return ;
        } R tmp=_upper_bound(lst+1,n,res),f=0;
        for(R i=tmp;i<=n;++i) if(!v[i]&&f!=a[i]) {
            v[i]=true; dfs(stk,res-a[i],i); v[i]=false; f=a[i];
            if(flg) return; if(res==a[i]||res==len) return ;
        } 
    }
    signed main() {
        R N=g();
        for(R i=1,x;i<=N;++i) {
            x=g(); if(x>50) continue;
            a[++n]=x,sum+=x;
        } sort(a+1,a+n+1,greater<int>());
        for(len=a[1];len<=sum>>1;++len) {
            if(sum%len) continue; cnt=sum/len; 
            memset(v,false,sizeof(v)); v[1]=true;
            dfs(1,len-a[1],1); if(flg) break;
        } printf("%d\n",flg?len:sum);
    }

--------------------

2019.04.25

转载于:https://www.cnblogs.com/Jackpei/p/10771199.html