題意：給定一堆不定長度的小棒子，問他們能否構成一個正方形。

解題思路：最開始寫的時候把題意弄錯了，以為只要能夠從中取出一部分構成矩形即可。。。。

這里注意一下幾個剪枝的地方：

1）要把所有的棒子都用上且組成正方形，那么sum % 4 = 0；

2）如果棒子長度小于4，肯定是不行的

3）如果棒子中有長度大于sum/4的，肯定是組成不了正方形的。

注意：對棒子長度進行排序時，從大到小的順序用時更少。

AC:

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;int len[25],n,sum; bool used[25],flag;bool cmp(int a,int b) {return a > b; }bool dfs(int cur,int tmp,int index) //cur表示當前所取的木棍編號，tmp表示當前邊的長度，index表示4條邊中的編號 {if(index > 4) return true;if(tmp + len[n] > sum) return false;for(int i = cur+1; i <= n; i++){if(used[i] == true) continue;if(tmp + len[i] > sum) continue;used[i] = true;if(tmp + len[i] == sum) {if(dfs(0,0,index+1))return true;}else // tmp + len[i] < sum{if(dfs(i,tmp+len[i],index))return true;}used[i] = false;}return false; }int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&len[i]);sort(len+1,len+1+n,cmp);sum = 0;for(int i = 1; i <= n; i++)sum += len[i];memset(used,false,sizeof(used));if(sum % 4 != 0 || n < 4 || sum / 4 < len[1])printf("no\n");else{sum /= 4; if(dfs(0,0,1))printf("yes\n");else printf("no\n");}}return 0; }

總結

以上是生活随笔為你收集整理的poj 2362（剪枝）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。