题目链接
大致题意：
给定一堆不定长度的小棒子，问他们能否构成一个正方形。
解题思路：
POJ1011的热身题，DFS+剪枝
本题大致做法就是对所有小棒子长度求和sum，sum就是正方形的周长，sum/4就是边长side。
问题就转变为：这堆小棒子能否刚好组合成为4根长度均为side的大棒子
不难了解，小棒子的长度越长，其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少，这就是灵活性的体现。
由此，我们首先要对这堆小棒子降序排序，从最长的棒子开始进行DFS
剪枝，有3处可剪：
1、 要组合为正方形，必须满足sum%4==0；
2、 所有小棒子中最长的一根，必须满足Max_length <= side，这是因为小棒子不能折断；
3、 当满足条件1、2时，只需要能组合3条边，就能确定这堆棒子可以组合为正方形。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; bool vis[21]; int stick[21]; int n; int side; bool cmp(int a, int b) { return a > b; } bool dfs(int num, int len, int s)//s为搜索起点 { if (num == 4) return true; for (int i = s; i < n; i++) { if (vis[i]) continue; vis[i] = true; if (len+stick[i] < side) { if (dfs(num, len+stick[i], i)) //这里解释游戏为什么有搜索起点这一变量，只有这用到了，如果len+stick[i] > side了 //因为是非升序，len+stick[i-1] > side必然成立，从0开始就是浪费时间 return true; /*开始这里我直接 return dfs(num, len+stick[i], i)；貌似这样也可以， 但的的确确是错的,直接返回会导致我们少判很多种情况*/ } else if (len+stick[i] == side) { if (dfs(num+1, 0, 0)) return true; //这里同上 } vis[i] = false; } return false; } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); int sum = 0; for (int i = 0; i < n; i++) { scanf("%d", &stick[i]); sum += stick[i]; } side = sum/4; sort(stick, stick+n, cmp); if (sum % 4 || side < stick[0]) //这里也可以去掉一些情况 { puts("no"); continue; } memset(vis, false, sizeof(vis)); if (dfs(1, 0, 0)) puts("yes"); else puts("no"); } return 0; }
