注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

poj 1011  

2012-11-30 13:34:11|  分类: ACM-poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://poj.org/problem?id=1011
题意及解法:
题意:一堆等长的木棒,被剪成了若干段,现在知道有n段被减后的木棒,问最小的原始木棒长度
一道很经典的dfs:看完题后,做法都能想到,求出给出的所有木棒的长度和sum,从最长一根木棒的长度i开始枚举到sum,如果sum%i==0,则设原始长度为i,进行dfs,如果能找到所有木棒都能凑成原始长度的解 则输出当前的木棒长度,结束。

一般的dfs会超时,这里需要各种剪枝:
1.把木棒从小到大排序,越长的木棍对后面木棍的约束力越大,按木棍长度从大到小搜索,这样就能在尽可能靠近根的地方剪枝。
2.如果搜索失败,而且当前木棒是最后一根木棒,即当出现加上某根木棍恰好能填满一根原始木棍,就不用继续搜索了,直接退出当前的枚举。
3.如果搜索失败,而且当前木棒是第一根木棒,即当前剩余的长度等于设定的原始长度,就不用继续搜索了,直接退出当前的枚举。
4.跳过重复长度的木棍,如果当前木棒搜索失败,则它后面和其相等的木棍也无法得出合法解

写了两种不同的dfs方法:
方法一:

/*
* fudq.cpp
*
* Created on: 2012-11-30
*/

#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
int n,sum,f[102];
bool vis[102];

bool cmp(int a,int b){return a>b?true:false;}

bool dfs(int unused,int left,int len)
{//unused表示未使用的木棒根数,left表示当前木棒剩余长度,len表示设定的原始长度
if(unused==0 && left==0)//如果木棒都用完了,且没有当前的木棒没有剩余,则表示搜索成功
return true;
if(left==0)//如果当前木棒没有剩余长度,则表示当前搜索成功,进行下一根的搜索,left设为len
left=len;
for(int i=0;i<n;i++)
{
if(vis[i] || f[i]>left)//如果第i根木棒已被用或者长度大于剩余的,为不符合要求要pass
continue;
vis[i]=true;
if(dfs(unused-1,left-f[i],len))//将该木棒加上,进行下一步搜索
return true;
vis[i]=false;
//搜索失败,如果该木棒长度等于剩余的长度,也就是该木棒是最后一根,后面的不需要再考虑了(后面的会更短);如果剩余的长度等于当前设定的长度,也就是该木棒是第一根,后面的也不需要再考虑
if(left==f[i] || left==len)
break;
while(f[i+1]==f[i])//除重,如果当前木棒不符,后面相同的木棒也不符
i++;
}
return false;
}

int main()
{
int i,flag;
while(scanf("%d",&n)!=EOF && n!=0)
{
for(i=0,sum=0;i<n;i++)
{
scanf("%d",&f[i]);
sum+=f[i];
}
memset(vis,false,sizeof(vis));
sort(f,f+n,cmp);//从大到小排序
for(i=f[0],flag=0;i<=sum/2;i++)
{
if(sum%i!=0)
continue;
if(dfs(n,0,i))
{
printf("%d\n",i);
flag=1;
break;
}
}
if(flag==0)
printf("%d\n",sum);
}
return 0;
}


方法二(效率较高):

/*
* fudq.cpp
*
* Created on: 2012-11-29
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
int n,sum,bian,f[102];//bian表示原始边的长度
bool vis[102];

bool cmp(int a,int b){return a>b?true:false;}
//!不可以写成return a-b;否则会内存访问错误

bool dfs(int sta,int left,int len)
{//sta表示搜索的起点;left表示未拼成的木棒总长度,初值是sum;len表示当前搜索时需要的边长度
if(left==len)//当剩余木棒总长等于当前边长,即表示搜索成功
return true;
for(int i=sta;i<n;i++)
{
if(vis[i] || f[i]>len)//如果该点已经访问或者长度大于当前边长则pass
continue;
vis[i]=true;
if(f[i]==len && dfs(0,left-f[i],bian))//如果第i条边长等于当前边长,即表示最后一根,则可以从头开始找下一根原始木棒,且能搜索成功的话返回true
return true;
else if(dfs(sta+1,left-f[i],len-f[i]))//从下一起点搜索,且能搜索成功的话返回true
return true;
vis[i]=false;//搜索失败
if(f[i]==len || len==bian || left==sum)//如果是当前木棒是最后一根;所需的边长等于原始边长;剩余的木棒和等于木棒总和 则终结搜索
return false;
while(f[i+1]==f[i])//去重,如果当前的棒长度不符合要求的话,那么后面相同长度的当然也不行
i++;
}
return false;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int i,flag;
while(scanf("%d",&n)!=EOF && n!=0)
{
for(i=0,sum=0;i<n;i++)
{
scanf("%d",&f[i]);
sum+=f[i];
}
memset(vis,false,sizeof(vis));
sort(f,f+n,cmp);//从大到小排序
for(i=f[0],flag=0;i<=sum/2;i++)
{
//从最大的一条边开始遍历,设为原始木棒的长,记录在变量bian上
bian=i;
if(sum%bian!=0)//如果原始边长不能整除总和,肯定不符合要求
continue;
if(dfs(0,sum,bian))
{
printf("%d\n",i);
flag=1;
break;
}
}
if(flag==0)
printf("%d\n",sum);
}
return 0;
}


  评论这张
 
阅读(129)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018