poj 1011 Sticks
2023-04-18 12:34:12 时间
题意:有若干根一样长的棍子,然后将其随机地截断成n跟不同长短的小棍子;给你这n根棍子,让你求原来的棍子可能是多长,并且要求其长度最小。
题解:很经典的深搜剪枝。需要几个剪枝就不会TLE了。根据给定假设长度用dfs去判断 这一步实现应该不是问题。(直接排序后从大往小的扫一遍过去判断是不行的;一开始就wa这,,,后面才想到深搜=_=...)直接列出所需要的几个剪枝的地方: (1)先将n根小棍子从大到小排序。 (2)以假设长度从最大的棍子长度Max到总和sum遍历;如果sum%temp==0,则对假设长度temp进行dfs。 (3)在对假设长度temp进行dfs的时候,是要判断到sum/temp根temp长度都能拼成才算true的;所以只要判断到一根temp长度的棍子是拼不成的,那么后面剩下的若干根就不必判断了直接跳出。
详细见代码注释:
1 /** 2 * @author Wixson 3 */ 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 #include <algorithm> 9 #include <queue> 10 #include <stack> 11 #include <vector> 12 #include <utility> 13 #include <map> 14 #include <set> 15 const int inf=0x3f3f3f3f; 16 const double PI=acos(-1.0); 17 const double EPS=1e-8; 18 using namespace std; 19 typedef long long ll; 20 typedef pair<int,int> P; 21 22 int n,sum,Max,cnt; 23 int a[70]; 24 int book[70]; //标记数组 25 bool cmp(int a,int b) 26 { 27 return a>b; 28 } 29 //pos为当前在a的位置,left代表还剩几根没判断,len代表当前判断的这根还有多少长度要拼 30 int dfs(int pos,int left,int len) 31 { 32 if(len==0) 33 { 34 if(left==1) 35 { 36 return 1; 37 } 38 else 39 { 40 return dfs(0,left-1,Max); 41 } 42 } 43 // 44 for(int i=pos;i<n;i++) 45 { 46 if(a[i]>len) continue; 47 if(book[i]) continue; 48 book[i]=1; 49 if(dfs(pos+1,left,len-a[i])) 50 { 51 return 1; 52 } 53 book[i]=0; 54 // 55 if(len==Max) return 0;//最重要的剪枝,如果假设长度有一根拼不成就直接跳出dfs 56 // 57 while(i+1<n&&a[i]==a[i+1]) i++;//当前a[i]拼不成,那么后面跟其相同长度的都跳过 58 } 59 // 60 return 0; 61 } 62 int main() 63 { 64 //freopen("input.txt","r",stdin); 65 while(scanf("%d",&n)&&n) 66 { 67 flag=0; 68 Max=-inf; 69 sum=0; 70 for(int i=0; i<n; i++) scanf("%d",&a[i]),sum+=a[i],Max=max(Max,a[i]); 71 // 72 sort(a,a+n,cmp); //从大到小排序 73 // 74 while(true) 75 { 76 if(sum%Max==0) //取余不为0的话肯定就不用判断了 77 { 78 cnt=sum/Max; //要判断cnt根 79 memset(book,0,sizeof(book)); 80 if(dfs(0,cnt,Max)) break; 81 } 82 // 83 Max++; 84 } 85 printf("%d ",Max); 86 } 87 return 0; 88 }
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击