贴题目
Square
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 24604 | Accepted: 8449 |
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".
一道和1011很像的剪枝，在做了1011之后我写了这道题，结果不幸的wa了。所以说，1011的测点很水QAQ
读题后发现以下剪枝：
1、如果所有木棍和加起来不能被4整除，那么不能构成square;
2、将所有木棍和除以4的值（边长）保存，如果子段中的最大长度大于这一值，那么不能构成square;
3、与1011同理，同一长度的木棍不需重复判断；
4、将木棍从大到小开始找，因为越小的木棍灵活度越高。
分析可知，如果已经构成了3条边符合要求，那么一定能构成一个正方形。所以在进行第四边查找时，我们可以直接确定可以构成正方形。
代码如下：
#include<cstdio> #include<algorithm> #include<cstring> bool flag,zt[25]; int n,m,a[25],sum,l,mm,i; using namespace std; bool cmp(const int a,const int b){ return a>b; } void dfs(int num,int len,int now){ if(flag)return ; if(num==4){ flag=true; return; } if(len==sum){ dfs(num+1,0,1); if(flag)return ; } int i; for(i = now; i <= mm ; ++i){ if(!zt[i]&&len+a[i]<=sum){ zt[i]=true; dfs(num,len+a[i],i+1); zt[i]=false; if(flag)return ; } } return ; } void start(){ sum=0; memset(a,0,sizeof(a)); flag=false; i=0; } int main(){ scanf("%d",&n); while(n--){ start(); scanf("%d",&m); mm=m; while(m--){ ++i; scanf("%d",&a[i]),sum+=a[i]; } sort(a+1,a+mm+1,cmp); if(sum%4||a[1]>sum){ printf("no "); continue; } sum/=4; memset(zt,0,sizeof(zt)); dfs(0,0,1); if(flag)printf("yes "); else printf("no "); } return 0; }
dfs的习题重要的就是剪枝，拿到题目一定要多分析，尽可能多地找出不必要的枝，来提高时间效率。博主自己还要注意的就是细心，总是出一些没有必要的小毛病，希望能改掉这个毛病。
今天写的比较匆忙，不足的地方麻烦大家帮我提出来了~嗯，以后还是要加强练习。