poj 1011 Sticks

  题意：有若干根一样长的棍子，然后将其随机地截断成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 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
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)
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+11]) 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"%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\n",Max);
86     }
87     return 0;
88 }
dfs搜索

相关

docker-compose fastdfs

力扣530题（二叉搜索树的最小绝对差）

hdfs的写入过程和读取过程

快速排序与随机构建二叉搜索树

PyCharm2021使用教程 ---9、PyCharm中的搜索技巧（文件/函数/内容）

广度优先搜索复习笔记

无人机视觉导航搜索资料

find 语句过滤掉某个目录搜索

C#集成FastDFS断点续传

分布式文件服务器FastDFS

Linux搜索指定目录中所有文件的内容

大数据学习之旅1——HDFS版本演化

标签