木棒

木棒(大的拼好的)!=木棍(小的砍碎的)

算法 dfs+剪枝

dfs思路

其实dfs问题也可以像动态规划一样标记状态

  dfs(u,cur,start) 表示的是当前已经排好u根长度为len的木棍，现在我要排
  的这个木棍已经有cur长度了，我要从start根木棍开始找时候可以找到一组合适的

tip1:用反证法思考剪枝的操作

递归剪枝的核心思考 减少递归的深度

顺序剪枝 如何减少递归的深度

先放大的 后面小的可选择性小 深度就会降低

冗杂剪 (减少因顺序不同而产生的多余) 321 123 231

将数组编号小的放在一根木棒的前面

可行性剪 提前预判不可行直接放弃

①如果某一根木棍放在最新木棒的‘第一’的位置不可以那么此方案不可行
```
明白一个既定事实“该木棍放在最新木棒不可行”
反正法
假设这种方案可行那么这根木棍一定放在后面的其他木棒之中由于前面冗杂剪的

缘故这根木棍一定会放在后面木棒的第一位而这样摆出来的木棒是与最开始的木棒

是等效的那么该方案不可行
②如果某一根木棍放在最新木棒的最后恰好是目标长度但是不可行那么此方案不可行
反正法
假设此方案可行那么一定会有后面某几个木棍之和与该木棍等长的

替代该木棍那么二者不就又构成等效关系了

(一根长木棍的可行性要小于多根和等长的小木棍的)
```
③如果一个木棍失败与之等长的几个一定失败

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=64;

int sticks[N];
bool st[N];
int n,sum,length;

bool dfs(int u,int cur,int start)   //排到第u个木棍，该木棍长度为cur，从start开始枚举    
{

   /*dfs(u,cur,start) 表示的是当前已经排好u根长度为length的木棍
   ，现在我要排的这个木棍已经有cur长度了
   ，我要从start根木棍开始找时候可以找到一组合适的解*/
    if(u*length==sum)return true;   //DFS完成
    if(cur==length)return dfs(u+1,0,0);//该木棍已经用完
    for(int i=start;i<n;i++)        //枚举多种情况
    {
        if(st[i])continue;          //已经被访问过了
        int l=sticks[i];            //保存第i根木棍的长度
        if(l+cur>length)continue;   //如果加上后超出木棍长度
        st[i]=1;                    //标记为已用
        if(dfs(u,cur+l,i+1))return true;//DFS成功
        st[i]=0;                    //复原现场

        if(!cur)return false;       //所有木棒中最大的木棒(第一个木棒)放入失败，就一定失败
        //可行性剪 1
        if(cur+l==length)return false;//最后一根木棒放入后可以达到length却没有成功，就一定失败
        //可行性剪 2

        int j=i;                    //跳过相同部分
        while(j<n&&sticks[j]==l)j++;//跳过相同部分
        i=j-1;                      //因为这次循环后i要加一，所以先减一//可行性剪三

    }
    return false;                   //失败
}

int main()
{
    while(cin>>n,n)
    {
        sum=length=0;               //清空
        for(int i=0;i<n;i++)        //读入
        {
            int l;
            cin>>l;
            sticks[i]=l;
            sum+=l;                 //统计长度
            length=max(length,l);   //统计最大长度
        }
        sort(sticks,sticks+n);      //从小到大排序
        reverse(sticks,sticks+n);   //反过来，就是从大到小排序，从大的开始暴搜，方案数相对减少
        memset(st,0,sizeof st);     //清空
        while(true)
        {
            if(sum%length==0&&dfs(0,0,0))//如果k*length=sum,说明长度可以为length
            {
                cout<<length<<endl;
                break;
            }
            length++;               //枚举下一个长度
        }
    }
    return 0;
}