題大致做法就是對所有小棒子長度求和sum，sum就是正方形的周長，sum/4就是邊長side。

問題就轉變為：這堆小棒子能否剛好組合成為4根長度均為side的大棒子

?

不難了解，小棒子的長度越長，其靈活性越差。例如長度為5的一根棒子的組合方式要比5根長度為1的棒子的組合方式少，這就是靈活性的體現。

由此，我們首先要對這堆小棒子降序排序，從最長的棒子開始進行DFS

?

剪枝，有3處可剪：

1、? 要組合為正方形，必須滿足sum%4==0；

2、? 所有小棒子中最長的一根，必須滿足Max_length <= side，這是因為小棒子不能折斷；

3、? 當滿足條件1、2時，只需要能組合3條邊，就能確定這堆棒子可以組合為正方形。

<pre name="code" class="cpp">//Memory Time //244K 79MS #include<iostream> #include<algorithm> using namespace std;int cmp(const void* a,const void* b) //降序 {return *(int*)b-*(int*)a; }int n; //木棒數量 int side; //正方形邊長 bool dfs(int* stick,bool* vist,int num,int len,int s) //num:已組合的正方形的邊數 len:當前組合的邊已組合的長度,len<=side { //s:stick[]的搜索起點if(num==3) //剪枝3，當滿足剪枝1和2的要求時，只需組合3條side，剩下的棒子必然能夠組成最后一條sidereturn true;for(int i=s;i<n;i++){if(vist[i])continue;vist[i]=true;if(len+stick[i]<side){if(dfs(stick,vist,num,len+stick[i],i)) //繼續構建當前sidereturn true;}else if(len+stick[i]==side){if(dfs(stick,vist,num+1,0,0)) //構建新sidereturn true;}vist[i]=false;}return false; }int main(void) {int time;cin>>time;for(int t=0;t<time;t++){ int sum=0; //所有木棒長度之和cin>>n;int* stick=new int[n];bool* vist=new bool[n];for(int i=0;i<n;i++){cin>>stick[i];vist[i]=false;sum+=stick[i];} if(n<4 || sum%4!=0) //剪枝1，不能構成正方形{cout<<"no"<<endl;continue;}qsort(stick,n,sizeof(int),cmp); //降序排列，先組合長棒，因為長棒相對于短棒的組合靈活性較低side=sum/4; //邊長if(side<stick[0]) //剪枝2，side<max_stick{cout<<"no"<<endl;continue;}if(dfs(stick,vist,0,0,0))cout<<"yes"<<endl;elsecout<<"no"<<endl;delete stick;delete vist;}return 0; }

總結

以上是生活随笔為你收集整理的poj2362 DFS+剪枝的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。