poj1011(深搜+剪枝)

题意:给m根木棍,将它们重新拼成n根一样长的木棍,并使得n尽量大(即每个新木棍尽量短)。

解法:经典的搜索题目。从小到大枚举拼成的新木棍长度,每次枚举进行一次深搜。这题关键是如何剪枝。

1、当枚举的长度不能整除总长度的时候,剪枝;(这个很显然)

2、先将木棍从长到短排序,枚举时先尝试长的木棍。(先枚举长的可以使得搜索深度不至于过深)

3、深搜时,不要企图通过换掉一个新木棍的第一根来改变失败的局面(换掉第一根A,那么A也会在以后的新木棍中被使用,但是已经证明了A无法拼成了,所以不必再尝试下去了)

4、不要企图换掉新木棍的最后一根来改变失败的局面。(同理3)

5、如果一根木棍试过不行之后,不用再尝试将其换为之后一样长的木棍了。(很显然的剪枝)

代码:

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>

using namespace std;

#define eps 1e-8
typedef long long LL;

int n;
int num[100];
bool rem[100];
int position;
int ans=0;
int sum;
bool dfs(int finished,int next,int position,int a)
{
    if(finished==sum/ans)
        return true;
    if(position==n)
        return false;
    int before=-1;
    for(int i=position; i<n; i++)
    {
        if(rem[i]||next+num[i]>ans||num[i]==before) continue;
        rem[i]=1;
        before=num[i];
        if(next+num[i]==ans)
        {
            if(dfs(finished+1,0,0,0))
                return true;
            else
            {
                rem[i]=0;
                return false;
            }
        }
        if(dfs(finished,next+num[i],i+1,a+1))
            return true;
        rem[i]=0;
        if(a==0)
            return false;
    }
    return false;
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        sum=0;
        for(int i=0; i<n; i++)
            scanf("%d",num+i),sum+=num[i];
        sort(num,num+n);
        reverse(num,num+n);
        for(ans=1;; ans++)
        {
            if(sum%ans!=0)
                continue;
            memset(rem,0,sizeof rem);
            position=0;
            if(dfs(0,0,0,0))
                break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj1011(深搜+剪枝),布布扣,bubuko.com

时间: 05-05

poj1011(深搜+剪枝)的相关文章

UVA1374 - Power Calculus(迭代深搜+剪枝)

题目链接 题意:给出x和正整数n,问最少需要几次乘除法 可以得到n = x^m 思路:其实是关于指数的操作,即从1到m最少的步数.我们可以先确定最少步数m,然后进行迭代,迭代的过程也就是判断通过相加减所得到的数可以在m次操作中等于n,如果符合,m即为最小步数,如果不符合,m++,进行下一次迭代.迭代过程中要注意剪枝,即剩余的次数如果每次都是取最大值相加还是比n小的话,就直接跳出. 代码: #include <iostream> #include <cstdio> #include

hdu 1518 Square(深搜+剪枝)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1518 题目大意:根据题目所给的几条边,来判断是否能构成正方形,一个很好的深搜应用,注意剪枝,以防超时! 1 #include <iostream> 2 #include <cstdio> 3 #include<algorithm> 4 #include <cstring> 5 using namespace std; 6 int ap[30],visit[30]

POJ1011 (深搜+剪枝)

#include<iostream>//深搜学习(经典) #include<cstdio>//深搜可以作为面临多种选择时的不断尝试 #include<algorithm> #include<cstring> using namespace std; const int maxn = 105; int arr[maxn];//储存木棒长度 bool vis[maxn];//木棒是否被使用了 int n;//有n个数 bool cmp(const int a,c

poj1190 生日蛋糕(深搜+剪枝)

题目链接:poj1190 生日蛋糕 解题思路: 深搜,枚举:每一层可能的高度和半径 确定搜索范围:底层蛋糕的最大可能半径和最大可能高度 搜索顺序:从底层往上搭蛋糕,在同一层尝试时,半径和高度都是从大到小试 剪枝: ①已建好的面积已经超过目前求得的最优表面积,或者预见到搭完后面积一定会超过目前最优表面积,则停止搭建(最优性剪枝) ②预见到再往上搭,高度已经无法安排,或者半径无法安排,则停止搭建(可行性剪枝) ③还没搭的那些层的体积,一定会超过还缺的体积,则停止搭建(可行性剪枝) ④还没搭的那些层的

hdu1518(Square)深搜+剪枝

点击打开杭电1518 Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square? Input The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20,

ACM 海贼王之伟大航路(深搜剪枝)

"我是要成为海贼王的男人!" 路飞他们伟大航路行程的起点是罗格镇,终点是拉夫德鲁(那里藏匿着"唯一的大秘宝"--ONE PIECE).而航程中间,则是各式各样的岛屿. 因为伟大航路上的气候十分异常,所以来往任意两个岛屿之间的时间差别很大,从A岛到B岛可能需要1天,而从B岛到A岛则可能需要1年.当然,任意两个岛之间的航行时间虽然差别很大,但都是已知的. 现在假设路飞一行从罗格镇(起点)出发,遍历伟大航路中间所有的岛屿(但是已经经过的岛屿不能再次经过),最后到达拉夫德鲁

hdu 1455 sticks(经典深搜+剪枝技巧)

 题意:有一堆的木棒,长度不一,它们是有一些整齐的木棒截断而成的,求最小的木棒原始长度. 思路很简单深搜,但是直接深搜的话会tle,首先可以对木棒长度进行排序从大到小,优先使用长度长的木棒,加入当前长度不符合,考虑下一个木棒 其次如果长度为零的时候选择木棒失败,那么直接退出,实测加上这一剪枝就可以ac,这一剪枝可以帮助我们尽可能的在靠近树根处剪枝,所以优化效果很明显. 然后是如果这次选择的木棒长度和上次失败时的一样,那么剪枝. #include<cstdio> #include<cs

hdu 1010 Tempter of the Bone 深搜+剪枝

题意:在一个坐标内,给定起点和终点,问能否恰好在t时刻到达终点. 以前很少写搜索题,所以看到这个题,就按照普通的深搜写了一下,交上去超时了.后来在网上搜了一下才知道,要剪枝才行.可是,我以前从没写过剪枝,不知道怎么剪,就按照别人的思路往下想.看懂以后,我对剪枝的理解是:对于一些没有必要继续搜索的路径,不再往下深搜,提前返回到上一层.花了半天时间调试代码,终于AC了. 奇偶剪枝:根据题目,doggie必须在第t秒到达门口.也就是需要走t-1步.设doggie开始的位置为(sx,sy),目标位置为(

poj2531(深搜剪枝)

题意就是把节点分成A.B两组,节点间距C给了,要求解分组的方法,使得∑Cij (i∈A,j∈B)最大. 首先把所有节点都放在一组,然后采用深度优先搜索的方法,对每一个节点都做判断是否应该移到另一组去,判断的依据是移过去和不移过去哪个得到的和值比较大(这里移去B组后的计算方法就是加上该点和在A组中的所有点的间距,和减去原本就在B组中的所有点的间距),如果移过去变小了,那么则不移过去,并剪掉该条支路. DFS的本质就是枚举,一种递归的枚举.比如如果这个程序里面不剪枝的话就可以枚举到所有的分组情况.剪