大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
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); } }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118378.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...