其实,搜索可以认为是DFS,递归穷举所有情况的同时,通过剪枝舍去那些不可能的情况,来降低搜索的复杂度。
Sticks
Time Limit:1000MS |
|
Memory Limit:10000K |
Total Submissions:111462 |
|
Accepted:25581 |
Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him
and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5
#include<iostream>
using namespace std;
int n[100001];
bool used[100001];
void sort(int a[],int num){
for(int i=0;i<num-1;i++){
for(int j=0;j<num-i-1;j++){
if(a[j]<a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
bool concate(int unused,int left,int targetLen,int totalNum){
int i=0;
if(left==0&&unused==0){
return true;
}else if(left==0){
left=targetLen;
}
for(i=0;i<totalNum;i++){
if(!used[i]){
if(left<n[i])
continue;
left=left-n[i];
used[i]=true;
if(concate(unused-1,left,targetLen,totalNum))
return true;
}
}
used[i]=false;
return false;
}
int main(){
int sNum,sumLen=0;
while(cin>>sNum){
if(sNum==0)
break;
else{
for(int i=0;i<100001;i++){
used[i]=false;
n[i]=0;
}
for(int i=0;i<sNum;i++){
cin>>n[i];
sumLen+=n[i];
}
sort(n,sNum);
if(sNum==1){
cout<<n[0]<<endl;
continue;
}
for(int i=sumLen/n[0];(i>=2)&&(sumLen%i==0);i--){
if(concate(sNum,sumLen/i,sumLen/i,sNum)){
cout<<sumLen/i<<endl;
break;
}
}
}
sumLen=0;
}
}
顺便说下,并没有ac,但是,我测试了十来组数据,都是正确的,检查也看不出漏了哪些情况,所以,就这样贴上来吧
分享到:
相关推荐
搜索剪枝,全新讲解,覆盖面广,易懂,有使用价值,适用于noip,省赛,noi。。。。。
搜索方法中的剪枝优化,挺好的,希望对大家有用。
ACM中的回溯法:搜索是人工智能中的一种基本方法,也是信息学竞赛选手所必须熟练掌握的一种方法。我们在建立一个搜索算法的...本文所讨论的主要内容就是在建立算法的结构之后,对程序进行优化的一种基本方法——剪枝。
Angle搜索剪枝.doc 剪枝.doc 搜索的优化.doc 搜索顺序的选择.ppt 谈搜索算法的剪枝优化.doc 优化剪枝.doc
NULL 博文链接:https://chuanwang66.iteye.com/blog/1462968
很完整的搜索资料 oi必备 包含基础、剪枝、优化、博弈等
博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,...
支持以下的剪枝方法,代码一键运行,并配有md文档说明: (1) lamp 剪枝 (2) slimming 剪枝 (3) group slimming 剪枝 (4) group hessian 剪枝 (5) Taylor 剪枝 (6)Regularization 剪枝 等等
α—β剪枝搜索算法研究论文,不涉及具体的算法,α—β剪枝搜索算
搜索是计算机解题中常用的方法,它...因此,为了提高搜索的效率,人们想出了很多剪枝的方法,如分枝定界,启发式搜索等等。在竞赛中,我们不仅要熟练掌握这些方法,而且要因地制宜地运用一些技巧,以提高搜索的效率。
自己写的python决策树+随机森林,实现了预剪枝,后剪枝,并且包含了实验报告
博弈树的搜素算法,很全,包括渴望搜索,窗口等
人工智能小项目,2048棋盘游戏,Alpha-beta剪枝算法, Expectimax搜索 。 人工智能的课程作业,非常简单易懂,纯Javascript实现,运用Alpha-beta剪枝算法,
为在决策树剪枝中正确选择剪枝方法,基于理论...剪枝方法之一,但需要独立剪枝集;在同样精度情况下,ccP比REP产生的树小.如果训练数据集丰富,可以选 择砌强,如果训练数据集较少且剪枝精度要求较高,则可以选用PEP.
实现步骤: 1. yolov8s模型预训练 2. 模型稀疏化sparsity 3.剪枝 4. finetune 经过键枝后,finetune60个epoch达到原模型迭代52个epoch的mAP值0.78,模型的大小减少了2/5。
剪枝压缩剪枝压缩剪枝压缩剪枝压缩剪枝压缩剪枝压缩剪枝压缩剪枝压缩剪枝压缩
人工智能导论-第十课搜索剪枝与智能计算.ppt
YOLOv8模型剪枝源码