#算法/進階搜索
思路:
首先,最初始想法,將我們需要枚舉的長木棍個數計算出來,在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]);}}