hdu 1518 DFS+剪枝

Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output For each case, output a line containing “yes” if is is possible to form a square; otherwise output “no”.

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

题解：

意就是好多棍子，看能不能拼成正方形。 主要注意的有几点： 所有棍子都要用到，不能剩余 输入已经保证大于4根棍子了。所以无需判断可能小于3根棍子的情况 棍长的总数首先要是4的倍数，才能进行。否则直接输出 “no” 当前面前提满足以后，再满足3 根棍子拼好，就完工了。最后一根一定能拼好。 解法就是DFS——->深度优先搜索。DFS的思路就是一个图沿着一条路走下去，当走不下去的时候就回溯到上一结点再去走没有走过的岔路。 换算成数据结构的话，就要有一个“标记”来标记每个结点是否走过。DFS具体的实现方式，常见的一种就是：循环里面嵌套递归，这也算是一个DFS的框架。而剩下的要补充的“题眼”（也就是关键的地方）是要转移的状态。 参考：http://blog.csdn.net/guodongxiaren/article/details/23126997

代码：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; bool used[21]; int stick[21]; int t,goal; bool cmp(int a,int b) { return a>b; } bool dfs(int count,int pos,int res) { if(count==3) { return true; } for(int i=pos;i<t;i++) { if(used[i]) continue; used[i] = true; if(stick[i]==res) { if(dfs(count+1,0,goal)) return true; } else if(stick[i]<res) { if(dfs(count,i+1,res-stick[i])) return true; } used[i] = false; } return false; } int main() { int n; cin>>n; while(n--) { cin>>t; int sum=0; for(int i=0;i<t;i++) { cin>>stick[i]; sum+=stick[i]; } if(sum%4) { printf("no\n"); continue; } goal = sum/4; memset(used,false,sizeof(used)); sort(stick,stick+t,cmp); if(dfs(0,0,goal)) printf("yes\n"); else printf("no\n"); } return 0; }