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

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年.当然,任意两个岛之间的航行时间虽然差别很大,但都是已知的. 现在假设路飞一行从罗格镇(起点)出发,遍历伟大航路中间所有的岛屿(但是已经经过的岛屿不能再次经过),最后到达拉夫德鲁

深搜+剪枝 POJ 1724 ROADS

POJ 1724 ROADS Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12766   Accepted: 4722 Description N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and

HDU 1010 Temper of the bone(深搜+剪枝)

Tempter of the Bone Problem Description The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap

HDU 4876 ZCC loves cards【暴力+深搜+剪枝】

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4876 题意:给你N,l,k三个数,N代表N个数,从中任选k个数,然后 这k个数组成一个环,可以从这个环中选连续的1-k个数进行异或和 ,把所得到的值填充到l的后面,使得有一个数r让l-r之间所有的整 整数都被这些异或和填满,求最大的r,也许表达的不太清楚,其实 就是找一个最大的r,使得给定的l到这个r之间所有的数都能够被这些 异或和表示出来,注意异或和要求是连续的数异或的和. 分析:这道题我看了好久

hdu1455 Sticks 深搜 强剪枝

Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6035    Accepted Submission(s): 1704 Problem Description George took sticks of the same length and cut them randomly until all parts becam

【深搜加剪枝五】HDU 1010 Tempter of the Bone

Tempter of the BoneTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 64326    Accepted Submission(s): 17567 Problem Description The doggie found a bone in an ancient maze, which fascinated him a l