題目

思路

話不多說，直接上代碼

代碼

/*
AcW木棒-XMUOJ恢復破碎的符咒木牌 
搜索順序：從小到大枚舉最終的長度 len從前往后依次拼每根長度為len的木棍 
優化：
1.優化搜索順序：優先選擇深度短的來搜索，故從大到小去枚舉
2.排除冗余的方案：每一根長木棍的內部的編號遞增（排列方案變為組合方案）、
3.可行性剪枝：(1)當前第i根木棍失敗，跳過與當前木棍長度相等的其他木棍 (2)拼了幾根長木棍后，要拼新的木棍，第一個未被用過的木棍，如果作為新長木棍的第一段，無解，則直接回溯(3)拼了幾根長木棍后，要拼最后一段的木棍，當前小木棍加入使得當前長木棍滿足，但是剩余的木棒拼不出長木棒，無解，回溯 
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=70;
int w[N];//當前木棍的長度 
bool st[N];//是否用過
int sum,len; //當前木棍的總長度，枚舉的長度 
int n;
//u:當前正在構造第幾根長木棍
//cur：當前正在拼的長木棍的長度
//start: 當前長木棍中小木棍的下標 
bool dfs(int u,int cur,int start){if(u*len==sum)return true;//排完所有的小木棍了 if(cur==len)return dfs(u+1,0,0);//當前長木棍已經排好 for(int i=start;i<n;i++){if(st[i] )continue;//如果已經用過 if(cur+w[i]<=len){st[i]=true;if(dfs(u,cur+w[i],i+1)) return true;st[i]=false;//恢復現場 }if(!cur||cur+w[i]==len) return false;//到達這一步說明前面已經無解 int j=i;while(j<n&&w[i]==w[j])j++;//把與i相等的跳過i=j-1;//恢復下標 } return false;
}int main(){while(cin>>n,n){sum=len=0;for(int i=0;i<n;i++){cin>>w[i];sum+=w[i];len=max(len,w[i]);} sort(w,w+n,greater<int>()); memset(st,0,sizeof st);while(true){if(sum%len==0&&dfs(0,0,0)){cout<<len<<endl;break;}len++;}}return 0;
}