木棒

思路：经典剪枝，枚举len的长度

1.先排序从大到小选木棒

2.当一个位置上的木棒无法拼接时那么与其相同长度的木棒都不行

3.当拼一个木棍时，如果开头位置的木棒就无法拼接的话，可以直接跳过这种方案（替换第i根长棍的开头的木棒没有意义，因为满足剪枝1，2的话，放在头部的木棒A是你可选集合中的最长的木棒，不管对当前拼接的木棍选或者不选木棒A，在之后的搜索中A也必须放在其他木棍的头部）

4.当拼一个木棍时，如果结尾位置的木棒无法拼接的话，可以直接跳过这种方案（说明之前的就拼错了）

代码

//#pragma GCC optimize(2)
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int mod=1e9+7;
const int N=2e5+5;
const int inf=0x7f7f7f7f;int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}ll lcm(ll a,ll b)
{return a*(b/gcd(a,b));
}template <class T>
void read(T &x)
{char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-')op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op)x = -x;
}
template <class T>
void write(T x)
{if(x < 0)x = -x, putchar('-');if(x >= 10)write(x / 10);putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{ll res=1%p;while(b){if(b&1)res=res*a%p;a=1ll*a*a%p;b>>=1;}return res;
}
int vis[N];
int stick[N];
int sum,len,n;
bool dfs(int u,int cur,int star)
{//  cout<<u<<' '<<cur<<' '<<star<<endl;if(u*len==sum)return true;if(cur==len) return dfs(u+1,0,0);for(int i=star;i<n;i++){if(vis[i])continue;if(cur+stick[i]>len)continue;vis[i]=1;if(dfs(u,cur+stick[i],i+1))return true;vis[i]=0;if(!cur)return false;if(cur+stick[i]==len)return false;int j=i;while(j<n&&stick[i]==stick[j])j++;i=j-1;}return false;}
int main()
{while(cin>>n,n){//cout<<n;sum=0,len=0;for(int i=0;i<n;i++){int x;cin>>x;stick[i]=x;if(x>50)continue;sum+=x;len=max(len,x);}memset(vis,0,sizeof vis);sort(stick,stick+n,greater<int>());for(int i=0;i<n;i++)if(stick[i]>50)vis[i]=1;while(1){if(sum%len==0&&dfs(0,0,0)){cout<<len<<endl;break;}len++;}}return 0;}

木棒

思路：经典剪枝，枚举len的长度

1.先排序从大到小选木棒

2.当一个位置上的木棒无法拼接时那么与其相同长度的木棒都不行

3.当拼一个木棍时，如果开头位置的木棒就无法拼接的话，可以直接跳过这种方案（替换第i根长棍的开头的木棒没有意义，因为满足剪枝1，2的话，放在头部的木棒A是你可选集合中的最长的木棒，不管对当前拼接的木棍选或者不选木棒A，在之后的搜索中A也必须放在其他木棍的头部）

4.当拼一个木棍时，如果结尾位置的木棒无法拼接的话，可以直接跳过这种方案（说明之前的就拼错了）

代码

//#pragma GCC optimize(2)
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int mod=1e9+7;
const int N=2e5+5;
const int inf=0x7f7f7f7f;int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}ll lcm(ll a,ll b)
{return a*(b/gcd(a,b));
}template <class T>
void read(T &x)
{char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-')op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op)x = -x;
}
template <class T>
void write(T x)
{if(x < 0)x = -x, putchar('-');if(x >= 10)write(x / 10);putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{ll res=1%p;while(b){if(b&1)res=res*a%p;a=1ll*a*a%p;b>>=1;}return res;
}
int vis[N];
int stick[N];
int sum,len,n;
bool dfs(int u,int cur,int star)
{//  cout<<u<<' '<<cur<<' '<<star<<endl;if(u*len==sum)return true;if(cur==len) return dfs(u+1,0,0);for(int i=star;i<n;i++){if(vis[i])continue;if(cur+stick[i]>len)continue;vis[i]=1;if(dfs(u,cur+stick[i],i+1))return true;vis[i]=0;if(!cur)return false;if(cur+stick[i]==len)return false;int j=i;while(j<n&&stick[i]==stick[j])j++;i=j-1;}return false;}
int main()
{while(cin>>n,n){//cout<<n;sum=0,len=0;for(int i=0;i<n;i++){int x;cin>>x;stick[i]=x;if(x>50)continue;sum+=x;len=max(len,x);}memset(vis,0,sizeof vis);sort(stick,stick+n,greater<int>());for(int i=0;i<n;i++)if(stick[i]>50)vis[i]=1;while(1){if(sum%len==0&&dfs(0,0,0)){cout<<len<<endl;break;}len++;}}return 0;}