首先这道题目有两个非常重要的剪枝1、如果当前放的是木块的第一个那如果当前dfs不成立,那么直接返回false因为每一个木板必定属于一个块,当他放第一个的时候如果可以放其他的其实是已经固定了的了,如果当前不成立那么不存在队友可以和他一起站对。2、就是如果当前这个和前一次进行dfs的木板长度一样,就跳过。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 64;
int n, sum, s[MAXN+10], Len, tot;
bool vis[MAXN+10];
bool dfs(int _len, int up, int count){
if(count == tot) return true;
int tp=-10000000;
for(int i=up; i<n; i++){
if(!vis[i]){
if(s[i] == tp) continue;
tp = s[i];
vis[i] = true;
if(_len + s[i] == Len){
if(dfs(0, 0, count+1))
return true;
return vis[i] = false;
}
else if(_len + s[i] < Len){
if(dfs(_len+s[i], i+1, count))
return true;
if(_len == 0) return vis[i] = false;
}
vis[i] = false;
}
}
return false;
}
int main(){
while(~scanf("%d", &n) && n){
memset(vis, 0, sizeof vis);
sum = 0;
for(int i=0;i<n;i++){
scanf("%d", &s[i]);
sum += s[i];
}
sort(s, s+n);
for(Len=s[n-1]; Len<=sum; Len++)
if(sum % Len == 0){
tot = sum / Len;
if(dfs(0, 0, 0)){
printf("%d\n", Len);
break;
}
}
}
return 0;
}