首页 > 代码库 > HDU 1518 Square
HDU 1518 Square
题意:给你n根棍子跟它的边长,要你能用这些棍子组一个正方形
思路:回溯法
能组正方形条件:
1、棍子总长%4要等于0
2、不能出现棍子的长度大于正方形的边长
3、棍子数大于等于4
直接用回溯肯定会超时,所以我们需要来优化空间了
1、对于已使用的边,不能在它的子树中使用
2、由于题目是判断能不能组正方形,所以只要满足了条件,就直接结束!
所以AC代码:
#include <stdio.h> #include <string.h> int n,sum; int a[30],vis[30]; int flag; void dfs(int bian,int l,int k) { int i; if(bian==5) { flag=1; return ; } if(l==sum) { dfs(bian+1,0,0); if(flag) return ; } for(i=k;i<n;i++) { if(!vis[i]&&l+a[i]<=sum) { vis[i]=1; dfs(bian,a[i]+l,i+1); if(flag) return; vis[i]=0; } } } int main() { int t; scanf("%d",&t); while(t--) { int i; sum = 0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; } if(sum%4!=0) { printf("no\n"); continue; } sum=sum/4; for(i=0;i<n;i++) { if(a[i]>sum) break; } if(i!=n) { printf("no\n"); continue; } memset(vis,0,sizeof(vis)); flag=0; dfs(1,0,0); if(flag) printf("yes\n"); else printf("no\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。