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

好啊。。。太棒了。。。

---

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=; register char ch; while(!isdigit(ch=getchar())) ;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret;

}

int n,len,sum,cnt;

int a[];

bool v[],flg;

inline int _upper_bound(int l,int r,const int& dst) 
　　{while(l<r) {R md=l+r>>; if(a[md]<=dst) r=md; else l=md+;} return l;}

void dfs(int stk,int res,int lst) {

    if(!res) { if(stk==cnt) {flg=true; return ;} R i;

        for(i=;i<=n;++i) if(!v[i]) break;

        v[i]=true; dfs(stk+,len-a[i],i); v[i]=false; if(flg) return ;

    } R tmp=_upper_bound(lst+,n,res),f=;

    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=,x;i<=N;++i) {

        x=g(); if(x>) continue;

        a[++n]=x,sum+=x;

    } sort(a+,a+n+,greater<int>());

    for(len=a[];len<=sum>>;++len) {

        if(sum%len) continue; cnt=sum/len;

        memset(v,false,sizeof(v)); v[]=true;

        dfs(,len-a[],); if(flg) break;

    } printf("%d\n",flg?len:sum);

}

---

2019.04.25