hdu 1518 Square(DFS)
题目大意:所有的木棒连在一起,看能够组成一个正方形
也是一道比较经典的DFS,刚做过hdu1455(1455题解:1455题解)那道题,方法都一样,比这道难,现在做这道题感觉很easy
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,map[25],v[25]; int sum,length,flag; bool cmp(int x,int y) { return x > y; } void dfs(int num,int len,int pos) { if(num == 4) { flag = 1; return; } if(flag) return; for(int i = pos ; i < n ; i ++) { if(v[i]) continue; if(map[i] + len == length) { v[i] = 1; dfs(num + 1,0,0); v[i] = 0; } else if(map[i] + len < length) { v[i] = 1; dfs(num,map[i] + len,i + 1); v[i] = 0; while(map[i] == map[i + 1]) i++; } } } int main() { int i,T; scanf("%d",&T); while(T--) { scanf("%d",&n); sum = 0 ; for(i = 0 ; i < n ; i ++) { scanf("%d",&map[i]); sum += map[i]; } sort(map,map + n,cmp); if(sum%4) { printf("no\n"); continue; } memset(v,0,sizeof(v)); length = sum/4; flag = 0; dfs(1,0,0); if(flag) printf("yes\n"); else printf("no\n"); } return 0; }
补充:软件开发 , C++ ,