POJ 1011 sticks

题意简单说就是本来几根一样长的棍子 被小明乱切（乱切 没切中也是有可能的） 切成了n根小棍子

要你把n根小棍子恢复原样 可能有多组解

要求输出 每根棍子最短的情况时 棍子长度

据说是极为经典的dfs题

一开始真的不知道怎么搜好（辣鸡无力）闷了1个多小时无奈去看了一下题解 恍然大悟

看完自己敲一A后 细看一下 还是原来那些东西 dfs传参 之前积累的棍长 棍的数量 累加棍的位置

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <stack>

using namespace std;

int stick[70];
bool flag[70];
int len,sum,num,n;//len 棍长   sum所有棍子总长度   num棍数目   n小棍数目

bool dfs(int pre_len,int pre_num,int pos)
{
    if(pre_num==num) return true;
    for(int i=pos;i<n;i++)
    {
        if(flag[i]) continue;
        if(pre_len+stick[i]==len)
        {
            flag[i]=true;
            if(dfs(0,pre_num+1,0)) return true;
            flag[i]=false;//回溯
            return false;
        }
        else if(len>(pre_len+stick[i]))
        {
            flag[i]=true;
            if(dfs(pre_len+stick[i],pre_num,i+1)) return true;
            flag[i]=false;
            if(pre_len==0) return false;//这时 之前一根棍都没有   len>stick[i]
            while(i+1<n&&stick[i]==stick[i+1]) i++;//相邻一样的情况就不用算了
        }
    }
    return false;
}


int main()
{
    while(scanf("%d",&n),n)
    {
        num=sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&stick[i]);
            sum+=stick[i];
        }
        sort(stick,stick+n,greater<int>());
        memset(flag,false,sizeof flag);
        for(len=stick[0];len<=sum;len++)
        {
            if(sum%len) continue;//必须整除
            num=sum/len;//总共棍子的数量
            if(dfs(0,0,0))
            {
                printf("%d\n",len);
                break;
            }
        }
    }
    return 0;
}