acwing167. 木棒

题目

题解

剪枝

• 搜索顺序的优化：我们可以按照小木棍的长度进行排序，从大到小，若填上最长的之后没有可以匹配的话，那么这个长度绝对是不合法的。（大块一定比小块需要搜索的次数少）

• 可以再小木棒的长度上考虑剪枝。最长是sum，最短是最长的小木棍的长度，而且小木棒的长度一定是sum的因数，我们可以有选择的选择长度进行dfs。

• 在上面已经排好序的情况下，限制小木棍加入到木棒中的编号，保证加入进来的木棍的长度是递减的，（长的必须比短的先加入到正在拼凑的木棒里来）这样子的话可以避免重复搜索。

• 若当前 长度拼接失败，则后面所有相等的都会失败

• 如果放第一根木棒和放最后一根木棒都失败了，那么该长度一定不合法。（反证假设放在第一根或者最后一个不合法，然后我们将它放在其他位置合法了，但是我们可以通过交换，将这个位置换到第一根或者最后一根，那么冲突）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100;
int n,length,sum;
int w[N];
bool st[N];
bool dfs(int u,int cur,int start){
    if(u*length==sum)return true;
    if(cur==length)return dfs(u+1,0,0);
    for(int i=start;i<n;i++){
        if(st[i]||cur+w[i]>length)continue;
        st[i]=true;
        if(dfs(u,cur+w[i],i+1))return true;
        st[i]=false;
        
        if(!cur||cur+w[i]==length)return false;
        int j=i;
        while(j<n&&w[i]==w[j])j++;
        i=j-1;
    }
    return false ;
    
}
int main(){
    while(cin>>n,n){
        memset(st,0,sizeof st);
        sum=0;
        for(int i=0;i<n;i++){
            cin>>w[i];
            sum+=w[i];
        }
    
        sort(w,w+n);
        reverse(w,w+n);
        length=1;
        while(true){
            if(sum%length==0&&dfs(0,0,0)){
                cout<<length<<endl;
                break;
            }
            length++;
        }   
    }
    return 0;
}