排除等效冗余
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 typedef long long ll; 5 #define gmax(a,b) a=max(a,b) 6 #define FOR(i,a,b) for(rg int i=a;i<=b;++i) 7 #define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++ 8 static char buf[100000],*pa(buf),*pb(buf); 9 10 inline int rd() 11 { 12 rg int x(0),w(1); 13 rg char c(gc); 14 while(c<'0' || c>'9') 15 { 16 if(c=='-') w=-1; 17 c=gc; 18 } 19 while(c>='0' && c<='9') x=x*10+c-48,c=gc; 20 return x*w; 21 } 22 23 const int N=70; 24 int a[N]; 25 bool vis[N]; 26 int mx,cc,len,cnt,n; 27 28 //p stick th u now length x:little stick th 29 bool dfs(int p,int u,int x) 30 { 31 if(p>cnt) return 1; 32 if(u==len) return dfs(p+1,0,1); 33 int lf=0; 34 FOR(i,x,n) 35 if((!vis[i])&&a[i]+u<=len&&a[i]!=lf) 36 { 37 vis[i]=1; 38 if(dfs(p,a[i]+u,i+1)) return 1; 39 vis[i]=0;lf=a[i]; 40 if(u+a[i]==len||u==0) return 0; 41 } 42 return 0; 43 } 44 45 int main() 46 { 47 n=rd(); 48 FOR(i,1,n) a[i]=rd(),cc+=a[i],gmax(mx,a[i]); 49 sort(a+1,a+n+1,greater<int>() ); 50 //FOR(i,1,n) cout<<a[i]<<" ";cout<<endl; 51 for(len=mx;len<=cc;++len) 52 { 53 if(cc%len) continue; 54 cnt=cc/len; 55 memset(vis,0,sizeof(vis)); 56 if(dfs(1,0,1)){cout<<len;break;} 57 } 58 return 0; 59 }