POJ2362
题意：给定各个长度，问能否组成正方形。
DFS：现在看来重要的是思想，像一个问题要分步去思考。
1：正方形边长大于4，总长除以4余数0
2：最大边长不能大于总长除以4
3：查找边长需要从大向小查找，需要排序，且查找到3个满足边长就成功。
// #include<iostream> #include<algorithm> using namespace std; int stick[25],vist[25]; int n,side; bool cmp(const int a,const int b) { return a > b; } int DFS(int num,int len,int s) { if(num == 3) return true; for(int i = s;i < n; i++){ if(vist[i] == true) continue; vist[i] = true; if(stick[i] + len < side){ if(DFS(num,len + stick[i],i)) return true; } else if(stick[i] + len == side){ if(DFS(num+1,0,0)) return true; } vist[i] = false; } return false; } int main() { int time; cin>>time; while(time--){ int sum = 0; cin>>n; for(int i = 0;i < n; i++){ cin>>stick[i]; vist[i] = false; sum += stick[i]; } if(n < 4 || sum %4 != 0){ cout<<"no"<<endl; continue; } sort(stick,stick + n,cmp); side = sum/4; if(side < stick[0]){ cout<<"no"<<endl; continue; } if(DFS(0,0,0)){ cout<<"yes"<<endl; } else cout<<"no"<<endl; } return 0; }
