首页 > 代码库 > POJ 1011 Sticks
POJ 1011 Sticks
DFS
题意是让你把这些木棍组合成长度相等的一些木棍。要求长度最短。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int a[65],n,sum,ans; bool v[65],ok; bool cmpa(int a,int b) { return a>b; } bool dfs(int num,int need,int total) { int i; if(need==0) { if(total==sum/ans-2)return 1; for(i=0;v[i];i++); v[i]=1; if(dfs(i+1,ans-a[i],total+1))return 1; v[i]=0; return 0; } else { if(num>=n-1)return 0; for(i=num;i<n;i++) { if(a[i]==a[i-1]&&!v[i-1]) continue; if(!v[i]&&a[i]<=need) { v[i]=1; if(dfs(i,need-a[i],total))return 1; v[i]=0; } } return 0; } } int main() { while(scanf("%d",&n),n) { sum=ans=0; for(int i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i]; sort(a,a+n,cmpa); memset(v,0,sizeof(v)); ok=0; for(ans=a[0];ans<=sum/2;ans++) { if(sum%ans==0) { v[0]=1; if(dfs(0,ans-a[0],0)) {printf("%d\n",ans);ok=1;break;} } } if(!ok) printf("%d\n",sum); } return 0; }
还有更强大的剪枝版本的:
#include<cstdio> #include<cstring> #include<cstring> #define MAX 64 int s[MAX],vis[MAX],n,len,sum; void input() { int i,j,temp; sum = 0; for(i=0;i<n;i++) { scanf("%d ",&s[i]); sum+=s[i]; } for(i=1;i<n;i++) for(j=0;j<n-i;j++) { if(s[j]<s[j+1]) { temp = s[j]; s[j] = s[j+1]; s[j+1] = temp; } } } bool dfs(int now_len,int i,int count) { if((count+1)*len==sum) { return true; } for(int k= i;k<n;k++) { if(vis[k]) continue; if(k&&!vis[k-1]&&s[k]==s[k-1]) continue; if(s[k]+now_len>len) continue; if(now_len+s[k]==len) { vis[k]=1; bool result = dfs(0,0,count+1); vis[k]=0; return result; } else if(now_len==0) { vis[k]=1; bool result = dfs(s[k],k+1,count); vis[k]= 0; return result; } else if(now_len+s[k]<len) { vis[k] = 1; bool result = dfs(s[k]+now_len,k+1,count); vis[k] = 0; if(result) return true; } } return false; } int main() { while(scanf("%d",&n),n) { input(); for(len=s[0];len<=sum;len++) { if(sum%len) continue; memset(vis,0,sizeof(vis)); if(dfs(0,0,0)) break; } printf("%d\n",len); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。