题目描述

给n个木棒问能否拼成正方形(不许弯折)

Sample Input
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

Sample Output
yes
no
yes

解题思路

1.总长度必须是4的倍数 2.最长边不能大于边长 3.满足1 2后找到了3条边就可以了

将所有的木棒递减排列从头开始搜索，这样dfs深度可能小一点。dfs顺序是拓扑序，就是说每次搜一个木棒时只需要向它右边的搜索就可以了。代码如下

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn = 22; int vis[maxn]; int s[maxn]; int n,sum; bool cmp(int x,int y) { return x>y; } bool dfs(int _sum,int start,int kase)//_sum:当前已经组成了多少长度 start:从哪里开始找 kase:已经拼成了几个 { if(kase == 3) return true; if(_sum == sum/4) if(dfs(0,1,kase+1)) return true; for(int i = start; i <= n ; i ++) { if(!vis[i]) { vis[i] = 1; if(dfs(_sum+s[i],i+1,kase)) return true; vis[i] = 0; } } return false; } int main() { int t; scanf("%d",&t); while(t--) { memset(vis,0,sizeof vis); sum = 0; scanf("%d",&n); for(int i = 1 ; i <= n ; i ++) { scanf("%d",&s[i]); sum += s[i]; } sort(s+1,s+n+1,cmp); if(sum%4 || s[n]>sum/4) { printf("no\n"); continue; } if(dfs(0,0,0)) printf("yes\n"); else printf("no\n"); } return 0; }