例一、数的划分

个人觉得最剪枝的方法是直接枚举答案 

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int n,m,ans;inline void dfs(int sum,int k,int last){    if(k==1)//可行性剪枝     {        ++ans;        re ;    }        inc(i,last,(n-sum)/k)//上下界剪枝         dfs(sum+i,k-1,i);}int main(){    rd(n);rd(m);    dfs(0,m,1);    printf("%d",ans);    re 0;}
       
      

例二、[NOI1999]生日蛋糕

疯狂剪枝，你就赢了

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)#define dec(i,l,r) for(int i=r;i>=l;--i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int n,m,ans=2147483647,minv[25],mins[25];inline void pre(){    inc(i,1,m)    {        minv[i]+=minv[i-1]+i*i*i;        mins[i]+=mins[i-1]+2*i*i;    }    }inline void dfs(int nowv,int nows,int dep,int lastr,int lasth){    if(!dep)    {        if(nowv==n)        ans=min(ans,nows);        re ;    }     if(nows+mins[dep]>=ans)re;//最优性剪枝一：当前表面积+上面层取最小表面积大于当前答案     if(nowv+minv[dep]>n)re ;//可行性剪枝：是否满足体积为N     if(2*(n-nowv)/lastr+nows>=ans)re ;//不等式放缩得到的最优性剪枝二     int nowmaxv=n-minv[dep-1]-nowv; //同下     dec(i,dep,min((int)sqrt(nowmaxv/dep),lastr-1))//枚举r    //上下界剪枝    //+搜索顺序优化     {        dec(j,dep,min(nowmaxv/i/i,lasth-1))//枚举h         dfs(i*i*j+nowv,2*i*j+nows,dep-1,i,j);    } } int main(){    freopen("in.txt","r",stdin);    rd(n),rd(m);    pre();        int nowmaxv=n-minv[m-1]; //当前层最大体积     dec(i,m,(int)sqrt(nowmaxv/m))//枚举r    {        dec(j,m,nowmaxv/i/i)        dfs(i*i*j,i*i+2*i*j,m-1,i,j);//最下层，表面积要加上底面积     }     printf("%d",ans);    re 0;}
       
      

例三、小木棍 

题目描述

乔碧萝殿下有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过5050。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

#include
       
        #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i) #define dec(i,l,r) for(int i=l;i>=r;--i)using namespace std;int n,maxx,a[66],use[66],k,x,sum,m,len,next[66]; inline int read(){    int date=0;char c=' ';    while('0'>c||c>'9')c=getchar();    while('0'<=c&&c<='9'){date=(date<<3)+(date<<1)+(c^48);c=getchar();}    re date;}void vv(int num,int last,int rest){    if(rest==0)//如果拼接好当前木棍     {        if(num==m-1)printf("%d",len),exit(0);//找到答案         inc(i,2,n)        if(!use[i])        {    use[i]=1;            vv(num+1,i,sum/m-a[i]);//进行下一轮             use[i]=0;break;    }                }        int l=last+1, r=len, mid;    while(l
        
         >1;        if(a[mid]<=rest) r=mid;        else l=mid+1;    }    inc(i,l,k)//上下界剪枝&&顺序     if(!use[i]&&a[i]<=rest)    {            use[i]=1;        vv(num,i,rest-a[i]);        use[i]=0;        if(rest==a[i] || rest==len) return; //当前木棍不可行 ，无论如何都不可行         i=next[a[i]];//跳过相同长度     }    re;}bool cmp(int a,int b){    re a>b;}int main(){//    freopen("testdata.in","r",stdin);    n=read();    inc(i,1,n)    {        x=read();        if(x<=50){a[++k]=x;sum+=x;            maxx=max(maxx,x);}    }        sort(a+1,a+k+1,cmp);//从大到小枚举     //优化搜索顺序         inc(i,1,k)    {        int j=i+1;        if(a[i]==a[j])++j;        next[a[i]]=j-1;    //优化搜索顺序     }        int i;use[1]=1;    for(i=maxx;i
        
       

例 4 Addition Chains

好好的一到迭代加深

#include
       
        #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i) #define dec(i,l,r) for(int i=l;i>=r;--i)using namespace std;long long n,m,a[1005],deep;template
        
         inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}inline bool dfs(int cnt){    if(cnt==deep)        re a[cnt]==n;    if(1ll*a[cnt]*(1<<(deep-cnt))
         
          n)break;    else if(a[i]+a[j]>a[cnt])    {        a[cnt+1]=a[i]+a[j];        if(dfs(cnt+1)) re 1;    }    re 0;}int main(){//    freopen("testdata.in","r",stdin);    a[1]=1;    while(2333)    {         scanf("%d",&n);        if(!n)re 0;        printf("1");        for(deep=1;;++deep)        if(dfs(1))        {            inc(j,2,deep)            printf(" %d",a[j]);            break;        }            printf("\n");    }     re 0;}
         
        
       

 

非要弄成普通深搜剪枝

#include
       
        #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i) #define dec(i,l,r) for(int i=l;i>=r;--i)using namespace std;int n,m,a[105],b[105],ans;template
        
         inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}inline void dfs(int cnt){    if(cnt>=ans) re;    if(a[cnt]==n)    {        inc(i,1,cnt)        b[i]=a[i];        ans=cnt;        re ;    }    for(int i=cnt;(a[i]<<1)>a[cnt];--i)    {        dec(j,i,1)        if(a[j]+a[i]<=a[cnt])break;        else if(a[i]+a[j]<=n)        {            a[cnt+1]=a[i]+a[j];            dfs(cnt+1);        }    }}int main(){//    freopen("testdata.in","r",stdin);    a[1]=1;a[2]=2;    while(scanf("%d",&n))    {     if(!n)re 0;        if(n==1)        printf("1");        else if(n==2)        printf("1 2");        else         {            ans=2147483647;            dfs(2);            inc(i,1,ans)            printf("%d ",b[i]);        }                printf("\n");    }     re 0;}