试题 算法训练 小木棍
2023-09-14 09:14:25 时间
试题 算法训练 小木棍
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
问题描述
RJ有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过 50。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。
输入格式
第一行为一个单独的整数 N 表示看过以后的小木柜的总数,其中 N<=60;
第二行为 N 个用空个隔开的正整数,表示 N 跟小木棍的长度。。
输出格式
输出文件仅一行,表示要求的原始木棍的最小可能长度。
样例输入
9
5 2 1 5 2 1 5 2 1
样例输出
6
提交代码:
#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
int a[100],book[100];
bool cmp(int x,int y)
{
return x>y;
}
int len,cnt;
int dfs(int num,int lasti,int l)
{
//num为拼好的个数,lasti为上一个的编号,l为已拼成的长度
if(num==cnt+1) //表示拼成了cnt根小木棍且小木棍没有剩余,符合题目所求
return 1;
if(l==len)//拼成一个len长度num+1
return dfs(num+1,1,0);
for(int i=lasti; i<=n; i++)//剪枝,当用木棍i拼接最初的木棍时,可以从第i+1后的木棍开始搜索,因为排序,前面的木棍已经用过了
{
if(!book[i]&&l+a[i]<=len) //保证当前长度加上正在选的小木棍长度不大于len,如果大于len就是没有小木棍可以拼成len长度的小木棍,不符合条件
{
book[i]=1;
if(dfs(num,i+1,l+a[i]))
return 1;
book[i]=0;//深搜搜索后要取消标记
if(l==0||l+a[i]==len)//剪枝,找不到能拼成len长度的木棍
return 0;
while(a[i]==a[i+1])//去重剪枝 相同长度的不符合条件的则不需再搜索
i++;
}
}
return 0;
}
int main()
{
scanf("%d",&n);
int s=0;
//排序,最初小木棍的长度一定大于等于砍断后的小木棍的最大的长度,并且小于所有小木棍的长度之和
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
s+=a[i];
}
sort(a+1,a+1+n,cmp);
//所有小木棍的长度之和为s,则拼成若干根的小木棍的长度一定能被s整除,否则就拼不成,因为拼成的小木棍必须是整数根
for(len=a[1]; len<=s; len++)
{
if(s%len==0)
{
cnt=s/len;
if(dfs(1,1,0))
break;
}
}
printf("%d\n",len);
return 0;
}
相关文章
- 蓝桥杯算法训练 最大体积 (gcd+完全背包)------C语言—菜鸟级
- 最全深度学习训练过程可视化工具(附github源码)
- 她用10年日记训练GPT-3,对话童年的自己,网友:AI最治愈的应用
- 仅需1% Embedding参数,硬件成本降低十倍,开源方案单GPU训练超大推荐模型
- 近万人围观Hinton最新演讲:前向-前向神经网络训练算法,论文已公开
- 有效融合语言模型、图神经网络,文本图训练框架GLEM实现新SOTA
- 训练多个epoch来提高训练模型的准确率
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-48 算法训练 关联矩阵
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-246 算法训练 猴子吃包子
- AAAI 2023杰出论文一作分享:新算法加持的大批量学习加速推荐系统训练
- 独家解密!B站up主用千亿级参数模型训练出的AI小姐姐,竟让骗子倒贴520
- 开源方案复现ChatGPT流程!1.62GB显存即可体验,单机训练提速7.73倍
- 134个预训练模型、精度高达85.1%,百度视觉算法最强基石PaddleClas全新升级
- 回到未来!用童年日记训练AI,这个程序员借助GPT-3实现了与“过去的自己”的对话
- MIT开发新型神经网络训练技术,打开AI决策黑箱
- 澳洲超市打工妹自费参加奥运走红 兼职三年每天训练3小时