小木棍

佚名 5年前 (2019-06-22) 算法 1838人围观抢沙发百度已收录

题目描述（洛谷1120）

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50，

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

思路
这题明显是一段一段拼接，要使用广搜或深搜，用广搜则必然导致时间浪费，当拼不上则应立即调整上一状态，则同级状态也应改变，用广搜明显不合适。所以深搜用递归。
因为小于等于50，首先想到了桶排序；用其他排序有些麻烦，因为需要不断排序与增删小木棍，当次数过多显然耗时过多，有sort函数也不划算。
. 枚举最多可能段数或最小可能长度。不论枚举段数还是长度，都要事先把预得到的长度或段数计算出来，然后递归。自然想到，k为最小可能长度，g为最大可能段数，用当前还差n个长度的就拼好一段（也可用当前段已拼接的长度）去递归是好实现的。即dfs(int k,int n,int c);(c为当前已拼接长度) 当n=0,dfs(k,k,c+1)即可，当c=g,则由于循环顺序，答案已出。

优化（dfs）

.显然枚举所有情况再用递归判断是否可行很浪费时间，再输入数据时统计sum，当g，k都为整数时在调用递归判断是否可行；
显然枚举所有情况再用递归判断是否可行很浪费时间，再输入数据时统计sum，当g，k都为整数时在调用递归判断是否可行；
从剩下的小木棍从大到小挑选出第一个不大于n的小木棍进行拼接，eg（挑5，有5,3,2肯定挑5），将较小较灵活组合的小木棍留下来。注意：当挑6，有5，4，2，1，有些木棍拼接需要1，所以有时要选4，2，不能因挑走5后，剩下的木棍无法拼接就终止以k为最小长度的递归判断。
当n=k时，向下一层dfs（k，n–i(当前选中木棍长度)，c）返回失败时，直接向上一层返回失败。(c为已拼接好的段数)因为当前要重新开始拼接新的长度为k的一段，下一层返回失败即当前选择的这根与剩下的小木棍无法拼接成长度为k的一段，直接返回失败。
当n=i(当前选中木棍长度)，向下一层dfs（k，k，c+1）返回失败时,直接向上一层返回失败。
输入数据时，记下最大的小木棍长度maxa，主函数枚举时直接从maxa枚举最小长度（枚举段数没有这样优势了）。大概就是这样迭代枚举长度，符合都是整数，调用dfs（flag为标记）

 1 void work(int k,int n,int c){
 2     if(c==g) flag=1;
 3     if(!n) {work(k,k,c+1);return;}
 4     for(int i=50;i>0&&!flag;--i){
 5         if(lenth[i]&&i<=n) {
 6             --lenth[i];
 7             work(k,n-i,c);
 8             ++lenth[i];
 9             if(n==k||n==i) return;
10         }
11     }
12 }

然而还是会超时的，洛谷数据更新了！！！！

再优化

没必要枚举长度循环到sum,而是sum/2,即 **for(int i=maxa;i<=sum/2;++i)**当迭代结束后，flag=1输出当前循环的i,否则输出sum。
还没完，范围优化，在录入数据时，记下有效数据最大值maxa,最小值mina，再向dfs中加入开始枚举的最大长度q，则对特殊数据有很大的优化效果。
不使用flag，在得到结果时还要在层层返回，浪费时间，直接打印k，exit(0);否则在最后就回到了主函数直接输出sum。
其实还可以手写输入代码。直接上源代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int N,sum,maxa,g,mina=69;
 4 int tiao[55];
 5 void read(){
 6     scanf("%d",&N);
 7     for(int i=1,j=0;i<=N;++i){
 8         int x;scanf("%d",&x);
 9         if(x>50)continue;
10         sum+=x;
11         if(x>maxa) maxa=x;
12         if(x<mina)mina=x;
13         tiao[x]++;
14     }
15 }
16 
17 void work(int k,int n,int c,int q){
18     if(c==g) {printf("%d",k);exit(0);};
19     if(!n) {work(k,k,c+1,maxa);return;}
20     for(int i=q;i>=mina;--i)
21         if(tiao[i]&&i<=n) {
22             --tiao[i]; work(k,n-i,c,i);++tiao[i];
23             if(n==k||n==i) return ;
24         }
25 }
26 
27 int main(){
28     read();
29     N=sum>>1;
30     for(int i=maxa;i<=N;++i){
31         if(sum%i==0){
32             g=sum/i;
33             work(i,i,0,maxa);
34         }
35     }
36     printf("%d",sum);
37     return 0;
38 }