【HDU - 1518】Square （经典的dfs + 剪枝）

题干：

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

题目大意：

给定一些长度各异的木棒，请问是否可能把它们连接成一个正方形？

解题报告：

   这题是非常经典的dfs剪枝问题，但是一直弄不懂为什么必须要搞成   “一次dfs凑三条边  ”才可以，不能把dfs的功能限制成 凑一条边，然后进行三次dfs吗？（反正我是wa了。。。逃）

ps：与这道经典的剪枝题 相见恨晚啊！！

AC代码：

#include<bits/stdc++.h>using namespace std; int n,sum; int a[55]; bool vis[55];bool dfs(int cur, int st,int res) {if(cur == 4) return 1;if(res < 0) return 0 ;if(res == 0) {int bg = 1;while(vis[bg]) ++bg;for(int i = bg; i<=n; i++) {if(vis[i]) continue;vis[i]=1; if(dfs(cur+1,i+1,sum/4-a[i])) return 1;vis[i]=0;}return 0;} // if(st > n) return 0;for(int i = st; i<=n; i++) {if(vis[i]) continue;vis[i]=1;if(dfs(cur,i+1,res - a[i])) return 1;vis[i]=0;}return 0; } bool cmp(const int & a,const int & b) {return a > b; } int main() {int t;cin>>t;while(t--) {scanf("%d",&n);sum=0;int flag=1;for(int i = 1; i<=n; i++) scanf("%d",a+i),sum+=a[i]; if(sum%4 != 0 ){printf("no\n");continue;}memset(vis,0,sizeof vis);sort(a+1,a+n+1,cmp);if(dfs(1,1,sum/4)) printf("yes\n");else printf("no\n");}return 0 ; }

wa代码：

#include<bits/stdc++.h>using namespace std; int n,sum; int a[55]; bool vis[55];bool dfs(int st,int res) {if(res < 0) return 0 ;if(res == 0) return 1 ;for(int i = st; i<=n; i++) {if(vis[i]) continue;vis[i]=1;if(dfs(i+1,res - a[i])) return 1;vis[i]=0;}return 0; } bool cmp(const int & a,const int & b) {return a > b; } int main() {int t;cin>>t;while(t--) {scanf("%d",&n);sum=0;int flag=1;for(int i = 1; i<=n; i++) scanf("%d",a+i),sum+=a[i]; if(sum%4 != 0 ){printf("no\n");continue;}memset(vis,0,sizeof vis);sort(a+1,a+n+1,cmp);int st = 1;for(int i = 1; i<=3; i++) {while(vis[st]) ++st;if(!dfs(st,sum/4)) {flag=0;break;} }if(flag) printf("yes\n");else printf("no\n");}return 0 ; }

ps：

求大神给个解释，，至今不知道为什么、、、

总结

以上是生活随笔为你收集整理的【HDU - 1518】Square （经典的dfs + 剪枝）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。