Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
给一个过所有数据的代码(包括bt数据 ),两处重要剪枝#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <queue> #include <map> #include <set> #include <vector> using namespace std; bool vis[65]; int tm[65]; int x; int flag; int n; void dfs(int deep,int len,int num) //deep用过木棒数,len当前选取到的长度,num当前小棒序号 { int i; if (flag) return ; if (len==0) { i=1; while(vis[i]) i++; //找到未用的最长的棒子 vis[i]=true; dfs(deep+1,len+tm[i],i+1); //选取下一根 vis[i]=false; //如果本递归退出了,说明当前选择拼凑X的方案不合法; return ; } if (len==x) { if (deep==n) //全部选完了,且都能合成长度为x的方案 flag=1; //成功结束标记 else dfs(deep,0,0); //继续下一根拼凑 return; } for (i=num;i<=n;i++) //从比当前小的木棒开始选 { if (!vis[i]&&len+tm[i]<=x) // 没选过且 长度拼在一起不超过x { if (!vis[i-1]&& tm[i]==tm[i-1]) continue;//上一跟一样的都不选,这跟必然不用勾选 //most important cut vis[i]=true; dfs(deep+1,len+tm[i],i+1); //继续选 vis[i]=false; if (tm[i]+len==x) return ; //由于是从大到小选取,如果这个刚好能凑成X的方案最终都不合法,那么必然无解.如果存在其他方案合法,例如较短的另外几根,但当前方案不合法,这是矛盾的 if (flag) return ; } } if (flag) return ; } bool cmp(int a,int b) {return a>b;} int main() { while(cin>>n&&n) { int sum=0; int i; for (i=1;i<=n;i++) { scanf("%d",&tm[i]); sum+=tm[i]; } sort(tm+1,tm+1+n,cmp); for (i=tm[1];i<=sum;i++) { if (sum%i) continue; flag=0; memset(vis,0,sizeof(vis)); x=i; dfs(0,0,1); if (flag) {printf("%d\n",i);break;} } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator