思路:
枚举可能的答案,由于题目要求的是求最小,从小到大开始枚举,最小可能是数组里最大的数,最大可能是数组里面所有数的总和。
拼接木棍的过程使用dfs,每次拼接一定找未使用过的最大的木棍进行拼接
做到以上,即可保证答案正确,但是速度还不够,需要进行剪枝。
剪枝1:如果当前小木棍是拼接的整个木棍中的第一个或最后一个,那么换用木棍不可能拼接成功
剪枝2:如果a[I]==a[I+1] 即换用一个相同大小的木棍,那么必不可能拼接成功,直接跳过,无须尝试拼接
有以上两个剪枝即可达到运行时间要求,AC本题
注意事项:
每次进行dfs之前需要将相应vis数组置为true,在之后将其置为false,进行回溯。
下面是附有详细注释的代码(这题还是边写代码边写注释吧,要不然记不住每一步自己在干嘛2333):
#include <bits/stdc++.h> using namespace std; int n; int a[65]; bool vis[65]; int sum=0;//记录砍过以后的小木棍总长度 //枚举可能的答案,如果sum%i==0答案才有可能正确,否则直接跳过 //并且答案一定比最长的砍过以后的木棍要长 bool cmp(int x,int y) { return x>y; } bool dfs(int k,int step,int len,int rest)//k为已经拼好的木棍数量,len为木棍长度,rest为剩余待拼长度 { if(k-1==n&&rest==0) return true;//木棍用完,并且拼好 else if(rest==0)//拼好了,木棍还没用完 { rest=len;//找一根新的棍子来拼 step=0; } else if(k-1==n)//木棍用完了,却拼不好,说明这个答案是错误的,没法拼好 return false; for(int i=step+1;i<=n;i++) { if(!vis[i]&&a[i]<=rest)//如果木棒没用过并且拼上这根木棒以后不会使整个木棒长度大于len { vis[i]=true; if(dfs(k+1,i,len,rest-a[i])) return true; vis[i]=false; if(len==rest||a[i]==rest) //头尾剪枝 break; while(a[i]==a[i+1]) i++;//换用的新木棒一定不能跟之前淘汰的木棒一样 } } return false;//如果枚举完以后都没有拼接成功,说明失败了 } int main() { scanf("%d",&n); int QWQW=0;//用于解决掉大于50的数据 for(int i=1;i<=n;) { scanf("%d",&a[i]); if(a[i]<=50) {sum+=a[i]; i++;} else QWQW++; } n-=QWQW; sort(a+1,a+1+n,cmp); for(int i=a[1];i<=sum;i++)//由于要求的是最小长度,所以从最小可能答案一直枚举到最大可能答案 { if(sum%i!=0) continue; if(dfs(1,0,i,i))//dfs检验这个答案是否正确,接下来完成dfs函数的编写 //如果正确,直接输出这个答案并且跳出循环 { printf("%d\n",i); break; } } }