| ||||||||||
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 |
Re:一组比较BT的数据!In Reply To:Re:一组比较BT的数据! Posted by:HEU_xueyan at 2012-03-05 20:46:08 这个完全没有回溯啊,能出来正确结果是运气啊 更BT的数据啊,为什么我的代码秒这组数据,还T > #include<iostream> > #include<algorithm> > #include <cstdio> > #include <cstring> > using namespace std; > int n,s[65],sum; > bool used[65]; > bool cmp(int a,int b) > { > return a>b; > } > bool dfs(int cnt,int now,int nowlen,int each) > { > if(now*each==sum) > return true; > for(int i=cnt;i<n;i++) > { > if(used[i]||(i&&!used[i-1]&&s[i]==s[i-1])) > continue; > if(nowlen+s[i]==each) > { > used[i]=false; > if(dfs(0,now+1,0,each)) > return true; > used[i]=false; > return false; > } > else if(nowlen+s[i]<each) > { > used[i]=1; > if(dfs(i+1,now,nowlen+s[i],each)) > return true; > used[i]=0; > if(now==0) > return false; > } > } > return 0; > } > int solve() > { > sort(s,s+n,cmp); > for(int res=s[0];res<sum;res++) > { > if(sum%res) > continue; > memset(used,false,sizeof(used)); > if(dfs(0,0,0,res)) > return res; > } > return sum; > } > int main() > { > //freopen("in.in","r",stdin); > while(scanf("%d",&n),n) > { > sum=0; > for(int i=0;i<n;i++) > { > scanf("%d",&s[i]); > sum+=s[i]; > } > printf("%d\n",solve()); > } > return 0; > } > /* > 64 > 40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40 40 > */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator