AcW木棒-XMUOJ恢复破碎的符咒木牌-DFS与剪枝
题目
思路
话不多说，直接上代码
代码
/*
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;
}