poj1011_sticks

最近计划好好刷一下poj上的题，打印了一下要刷的题集。决定先从深搜开始。第一道题是sticks，之前写过是参考网上的。今天又写了一边，权当回顾。

题目：给定n个等长木棒，将其随机断开得到m个短木棒(m>n)。现给定m个短木棒的长度，求原始木棒的最短长度len。

poj1011题目链接

这是一道dfs题目，比较经典。

主要思路 就是首先将所有的木棒按照长度做一个递减排序。令len的范围是 [ 短木棒的最长长度, 短木棒的长度和 ]。给定一个len值，进行dfs遍历。临界条件 是已组成的木棒数目 = 原始木棒的个数n。

注意

• 对于dfs题目，考虑使用全局变量和结构体进行数据的存储，比较方便。
• 对于循环输出，记得记得清空全局变量。

github默认讲tab解析为8个空格。所以为了美观，尽量将所用编辑器的tab设置为4个空格，或者禁用tab字符 (eg dev c++)。

个人代码如下。文末附原作者代码，注释比较详细。

#include<iostream>
#include<algorithm>
using namespace std;

struct Stick{
    int len;
    bool vis;
};

Stick sticks[67]; 
int sum=0,n=0,total=0,k=0;
bool cmp(Stick a,Stick b)
{
    return a.len>b.len;
}

bool dfs(int num,int len,int pos)
{
    if(num==total) return true;
    for(int i=pos+1;i<n;i++)
    {
        if(sticks[i].vis)  continue;
        if(len+sticks[i].len==k)
        {
            sticks[i].vis=true;
            if(dfs(num+1,0,-1)) return true;
            sticks[i].vis=false;
            return false;
        }else if(len+sticks[i].len<k)
        {
            sticks[i].vis=true;
            if(dfs(num,len+sticks[i].len,i)) return true;
            sticks[i].vis=false;
            if(len==0)
                return false;
            while(i+1<n && sticks[i].len==sticks[i+1].len)  i++;
        }        
    }
    return false;
}
    
int main()
{
    while(cin>>n && n)
    {
        sum=0;
        for(int i=0;i<n;i++)
        {
            cin>>sticks[i].len;
            sticks[i].vis=false;
            sum+=sticks[i].len;
        }
        
        sort(sticks,sticks+n,cmp);
        for(k=sticks[0].len;k<=sum;k++)
        {
            if(sum%k!=0) continue;
            total=sum/k;
            if(dfs(1,0,-1)) //第一个参数是1的原因是如果当前n-1个木棒可以拼接成功的话，那么第n个木棒一定可以拼接成功。
            {
                cout<<k<<endl;
                break;
            }
        }    
    }
    return 0;
}

因原作者代码注释比较详细，此处就不详细介绍了，直接放代码。

#include <iostream>
#include <algorithm>
using namespace std;

//total能组成的木棒的组数,l:组成的木棒的长度
int total,l;
//num:输入的整数，sum：总长度
int num,sum;
typedef struct
{
    int length;//木棒的长度
    bool mark;//木棒是否被使用过
}Sticks;
Sticks sticks[70];

bool cmp(Sticks a,Sticks b)
{
    return a.length>b.length;
}
//s 已组成的木棒数目,len已经组成的长度，pos搜索的木棒的下标的位置
int dfs(int s,int len,int pos)
{
    if(s==total)return 1;
    for(int i=pos+1;i<num;i++)
    {
        //如果这个木棒已经用过，则继续下一根
        if(sticks[i].mark)continue;
        if(len+sticks[i].length == l)
        {
            sticks[i].mark = true;
            if(dfs(s+1,0,-1))return true;
            sticks[i].mark = false;
            return false;
        }else if(sticks[i].length+len<l){
            sticks[i].mark = true;
            if(dfs(s,len+sticks[i].length,i))
            return true;
            sticks[i].mark = false;
            //剪枝：如果当前搜索时，前边的长度为0，而第一根没有成功的使用，
            //说明第一根始终要被废弃，所以这种组合必定不会成功
            //此处的剪枝必须有，因为这里的剪枝会节省很多的无用搜索，
            //我试了一下，此处剪枝省去就会超时的。。。。
            if(len==0)return false;
            //剪枝：如果当前和上一次搜到的木棒是一样长的则没必要再搜一次了
            while(sticks[i].length==sticks[i+1].length)i++;
        }
    }
    return false;
}

int main()
{

    while(cin>>num&&num!=0)
    {
        sum = 0;//标记为0
        for(int i = 0; i < num; i++)
        {
            cin>>sticks[i].length;
            sum += sticks[i].length;
            sticks[i].mark = false;
        }
        //将木棒按照长度从长到短的顺序排序
        sort(sticks,sticks+num,cmp);
        //从木棒的最长的那根开始搜索，因为最小的组合也会大于等于最长的那根
        for(l = sticks[0].length; l <= sum; l++)
        {
            //剪枝一：如果不能被整除说明不能组成整数根木棒，搜下一个
            if(sum%l!=0)continue;
            total = sum / l;//得到木棒总数目
            if(dfs(1,0,-1))
            {
                cout<<l<<endl;
                break;
            }
        }
    }
    return 0;
}