AcWing 167. 木棒
原题链接
中等
作者:
liebe_1
,
2024-03-29 11:38:26
,
所有人可见
,
阅读 8
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100;
int n;
int w[N];
bool st[N];
int sum , len;
//u:当前枚举到了第几根长木棒,cur: 我们当前正在拼的长木棍长度 , start:我们当前正在拼的长木棍要使用的小木棍的下标
bool bfs(int u,int cur,int start) {
if(u * len == sum)return true;//把所有的小木棍都拼好了并且满足条件
if(cur == len)return bfs(u+1,0,0);//当前要拼的长木棍拼好了,拼下一个长木棍
for(int i = start; i < n; i++) {
if(st[i])continue;//当前木棍用过了跳过
if(w[i] + cur <= len) {
st[i] = true;
if(bfs(u,w[i]+cur,i+1))return true;
st[i] = false;
}
//假如加上任意小木棍都无法满足长度为len,那么就是无解
if(!cur || cur+w[i] == len)return false;//作为第一个或者最后一个都不可能有解
int j = i+1; //相同的长度也没有解
while(j < n && w[i] == w[j])j++;
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 && bfs(0,0,0)) {
cout<< len<<endl;
break;
}
len++;
}
}
return 0;
}