题目链接:http://poj.org/problem?id=2362
题目大意:给出M条筷子,问是否能够拼凑成正方形,是则打印yes,否则no.
解题思路:范围4 <= M <= 20,可以直接用DFS,DFS需要剪枝,否则肯定超时.
剪枝:1.总数不能被4整除,直接打印 no;
2.最长的那个筷子大于平均数,直接打印 no;
***3.从某点出发,走了很多个点,如果会返回那么直接退出此次循环(因为出发点不满足题意);
4.返回之后(说明走此点不合题意),若for循环的下一个点的值和现在一样,那么跳过下一个点;
5.当可以构成3条长度等于average就直接退出打印yes;
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 21 int num,flag,t,n,m,average,visit[MAX],stick[MAX]; int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } void DFS(int start,int temp,int root) { int i,j; if(flag!=0) return ; if(temp==average) { num++; if(num==3) //剪枝5 { flag=1; return ; } j=0; while(visit[j]) //**如果从没有访问过的那个点开始 j++; DFS(j,0,j); return ; } for(i=start;i<n;i++) { if(visit[i]==0&&stick[i]+temp<=average) { visit[i]=1; DFS(i+1,temp+stick[i],root); //以下表示已经退回来了// 既还原现场!!! if(flag) //找到符合的就退出所有DFS return ; if(temp+stick[i]==average) //如果走的点总有把num++,那么退回来的时候要还原(num--) { num--; } visit[i]=0; while(stick[i]==stick[i+1]) //剪枝4 返回之后(说明走此点不合题意),若for循环的下一个点的值和现在一样,那么跳过下一个点 i++; } if(!visit[root]) //**剪枝3 从某点出发,走了很多个点,如果会返回那么直接退出此次循环 return ; } } int main() { int i,sum,max; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0,sum=0,max=0,average=0;i<n;i++) { scanf("%d",&stick[i]); sum+=stick[i]; if(stick[i]>max) max=stick[i]; } average=sum/4; if(sum%4!=0||max>average) //剪枝1,剪枝2 { printf("no\n"); continue; } memset(visit,0,sizeof(visit)); qsort(stick,n,sizeof(stick[0]),cmp); flag=0; num=0; DFS(0,0,0); if(flag==1) printf("yes\n"); else printf("no\n"); } return 0; }
注:原创文章,转载请注明出处