/*dfs，剪枝是關鍵。╮(╯▽╰)╭本來是想一根棍子 一個棍子的填充，遇到棍子不合適的就回溯。但是實驗 證明這絕對是剪錯方向的！正確的解法是。。。先尋找 第一根棍子合不合適，如果不合適就沒有必要找下去了， 這是關鍵點。這題堪稱剪枝之最啊~~~~~ */#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> using namespace std; #define M 100 typedef long long LL; int N,a[M],mark,vis[M],m; bool dfs(int num,int re,int dul) //當dul等于0，就是重新找棍子的開始 {if(num==1) return true;int p;for(int i=0; i<N; ++i){if(!vis[i]){if((p=re+a[i])<mark) //拼湊棍子 {vis[i]=1;if(dfs(num,p,i+1)) return true;vis[i]=0;if(dul==0) break; //如果這個棍子找不到，就沒有必要找下去了 }else if(p==mark) //拼湊成功 {vis[i]=1;if(dfs(num-1,0,0)) return true;vis[i]=0;break; //如果找不到這根新的棍子就沒有必要繼續下去了。 }}}return false; } bool cmp(int m,int n) {return m>n; } int main() { //freopen("abc.txt","r",stdin);while(~scanf("%d",&N)&&N){int sum=0;for(int i=0; i<N; ++i){scanf("%d",&a[i]);sum+=a[i];}sort(a,a+N,cmp);int mmd=a[0];while(1){while(sum%mmd!=0) //尋找可以被sum整除的數mmd++;memset(vis,0,sizeof(vis));mark=mmd;if(dfs(sum/mmd,0,0)) break;mmd++;}printf("%d\n",mmd);} }
?
