首页 > 其他 > 详细

深搜优化剪枝

时间:2019-06-09 11:49:28      阅读:133      评论:0      收藏:0      [点我收藏+]

之前做过不少深搜题,很多TLE,所以剪枝很重要,如何“未雨绸缪”,避免不必要的搜索树分支?

例题:

数的划分

将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。

例如:n=7,k=3,下面三种分法被认为是相同的。

1,1,5; 1,5,1; 5,1,1;

问有多少种不同的分法。 输出一个整数,即不同的分法。

由题意得,其分发出现重复数字组合则为同一种算法,那么保证1-k个数递增即可

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s;
int a[10];
void search(int k){
    if(n==0) return;
    if(k==m){
        if(n>=a[k-1]){
            s++;
            return;
        }
    }
    for(int i=a[k-1];i<=n/(m-k+1);i++){
        a[k]=i;
        n-=i;
        search(k+1);
        n+=i;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    a[0]=1;
    search(1);
    printf("%d",s);
}

 

深搜优化剪枝

原文:https://www.cnblogs.com/648-233/p/10992971.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!