首页 > 其他 > 详细

解题:洛谷1120 小木棍

时间:2018-10-12 20:26:48      阅读:171      评论:0      收藏:0      [点我收藏+]

题面

这个题剪枝比较多的说=。=

1.记录最长和最短的木棍,限制枚举的上下界

2.记录木棍的总长$tot$度,只在其能被枚举的长度整除时搜索

3.从长到短枚举长度(暂时好像没啥用)

4.每次(不是新的一根木棍时)从上次枚举的长度开始枚举(和3组合起来用的)

5.(强剪枝来了)如果是在尝试拼一根新木棍,那么只要没拼出来就拼不出来了(这个时候没有可以回溯的状态)

6.(也是一个强剪枝,和上面的一个道理)如果恰好拼出一根新木棍就拼不出来了,也是一定拼不出来了

技术分享图片
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int cnt[60];
 6 int n,rd,len,tot,num,maxx,mini=1e9;
 7 bool DFS(int noww,int lenh,int last)
 8 {
 9     if(noww==num) return true;
10     for(int i=last;i>=mini;i--)
11         if(cnt[i]&&lenh+i<=len)
12         {
13             cnt[i]--; int tmp=lenh+i;
14             if(tmp==len) {if(DFS(noww+1,0,maxx)) return true;}
15             else {if(DFS(noww,tmp,i)) return true;} cnt[i]++;
16             if(!lenh||lenh+i==len) return false;
17         }
18     return false;
19 }
20 int main ()
21 {
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++)
24     {
25         scanf("%d",&rd);
26         if(rd<=50)
27         {
28             cnt[rd]++,tot+=rd;
29             maxx=max(maxx,rd);
30             mini=min(mini,rd);
31         }
32     }
33     bool found=false;
34     for(int i=maxx;i<=tot;i++)
35         if(tot%i==0) 
36         {
37             len=i,num=tot/i;
38             if(DFS(0,0,maxx)) 
39             {
40                 printf("%d",i);
41                 found=true; break;
42             }
43         }
44     if(!found) printf("%d",tot);
45     return 0;
46 }
View Code

 

解题:洛谷1120 小木棍

原文:https://www.cnblogs.com/ydnhaha/p/9780181.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!