洛谷P1120 小木棍

#算法/进阶搜索
思路:
首先,最初始想法,将我们需要枚举的长木棍个数计算出来,在dfs中,我们先判断,此时枚举这根长木棍需要的长度是否为0,如果为0,我们就枚举下一个根木棍,接着再判断,此时仍需要枚举的木棍个数是否为0,如果为0,代表我们这种方案可行,直接打印长木棍长度,接着我们再枚举每一根小木棍,将还没有访问的长木棍,以及长度小于还需要的长度的小木棍dfs下去
但显然这种方法时间复杂度太高,需要剪枝,那么考虑如何剪枝呢?
1.首先,先判断我们小木棍的总长度是否能被长木棍的长度整除,如果可以,枚举这根长木棍.
2.优先枚举长度长的小木棍,这样可使得枚举上更加灵活
3.在我们枚举枚举短木棍时候,如果我们枚举上一根木棍的长度与此时准备枚举的短木棍长度相同,并且,上一根的短木棍方案不行,那么,我们无需再继续枚举这根小木棍.
4.如果此时小木棍的长度等于剩余需要的长度,并且此时这根短木棍不满足要求,那么直接返回

代码一 无法全部ac

#include<bits/stdc++.h>using namespace std;const int N=66;int a[N];int len[N];//记入相同长度小木棍个数int n;int sum;int d;//长木棍长度//u代表这根小木棍剩余长度,k代表还需要枚举长木棍个数void dfs(int u,int k){if(u==0){dfs(d,k-1);}if(k==0){cout<<d<<endl;exit(0);}for(int i=n;i>=1;i--){if(a[i]>u)continue;if(len[a[i]]==0)continue;len[a[i]]--;dfs(u-a[i],k);len[a[i]]++;if(a[i]==u)return;}}int main(void){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];len[a[i]]++;}sort(a+1,a+1+n);//剪枝2for(int i=a[n];i<=sum;i++){if(sum%i!=0)continue;//剪枝1d=i;dfs(i,sum/i);}}

在dfs中,我们是通过遍历每一个小木棍,来进行判断当前的小木棍是否可以拼接,但每次遍历的时候都会将所有的小木棍都会遍历一边,如果出现多个小木棍长度相同,我们会将所有长度相同的小木棍也遍历一边,会浪费许多时间,那么,我们思考,有什么其他的方法能减少这些时间的浪费呢?这时,我们可以考虑枚举小木棍的长度,我们先定义一个pre数组,存储每根短木棍的上一个比他短的小木棍,然后,在dfs中,我们每次只需要查找第一根最长且还有剩余量的小木棍即可,这样就可以避免寻找每一个小木棍的

#include<bits/stdc++.h>using namespace std;const int N=66;int a[N];int len[N];//记入相同长度小木棍个数int n;int pre[N];int sum;int d;//长木棍长度//u代表这根小木棍剩余长度,k代表还需要枚举长木棍个数,当前小木棍的长度void dfs(int u,int k,int p){if(u==0){dfs(d,k-1,a[n]);}if(k==0){cout<<d<<endl;exit(0);}p=min(p,u);while(p&&len[p]==0)p--;while(p){if(len[p]){len[p]--;dfs(u-p,k,p);len[p]++;if((p==u)||(u==d))return;}p=pre[p];}}int main(void){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];len[a[i]]++;}sort(a+1,a+1+n);//剪枝2for(int i=n;i>=1;i--){if(a[i]!=a[i-1]){pre[a[i]]=a[i-1];}}for(int i=a[n];i<=sum;i++){if(sum%i!=0)continue;//剪枝1d=i;dfs(i,sum/i,a[n]);}}