首页 > 代码库 > poj 2362 Square
poj 2362 Square
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
这个题可以说是poj1011的减弱版,只需要查一个值,不过在dfs时候的剪枝基本上是一模一样的
#include<map> #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x0f0f0f0f using namespace std; bool cmp(int x,int y) { return x>y; } int n,a[21]; bool vis[21]; bool dfs(int nowlen,int Len,int x,int num) { if (num==n) return true; int temp=0; for (int i=x;i<n;i++) { if (vis[i] || a[i]==temp) continue; vis[i]=true; if (nowlen+a[i]<Len) { if (dfs(nowlen+a[i],Len,i+1,num+1)) return true; else temp=a[i]; } if (nowlen+a[i]==Len) { if (dfs(0,Len,0,num+1)) return true; else temp=a[i]; } vis[i]=false; if (nowlen==0) break; } return false; } int main() { int t,sum; scanf("%d",&t); while (t--) { sum=0; memset(vis,0,sizeof(vis)); scanf("%d",&n); for (int i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; } sort(a,a+n,cmp); if (sum%4==0) { if (dfs(0,sum/4,0,0)) printf("yes\n"); else printf("no\n"); } else printf("no\n"); } return 0; }
作者 chensunrise
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。