hdu 1518 dfs+剪枝

时间：2023-01-13 14:56:36

题目大意：
几根棒子能否组成一个正方形

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

虽然不用pos直接从0开始枚举也可以有答案，但会超时，加个pos，以前dfs过的情况就不会再出现了，想起以前bc的一道题也是这样

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt;

 int a[];

 bool vis[];

 int len1;

 bool dfs(int len,int pos,int tot)

 {

     if(tot==)  return ;

     for(int i=pos;i<n;i++)

     {

         if(vis[i])  continue;

         if(len+a[i]==len1)

         {

             vis[i]=;

             if(dfs(,,tot+))  return ;

             vis[i]=;

         }

         if(len+a[i]<len1)

         {

             vis[i]=;

             if(dfs(len+a[i],i,tot))   return ;

             vis[i]=;

         }

     }

     return ;

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     scanf("%d",&tt);

     while(tt--)

     {

         scanf("%d",&n);

         len1=;

         for(i=;i<n;i++)

         {

             scanf("%d",&a[i]);

             len1+=a[i];

         }

         if(len1%!=||n<)      //数目小于4或者总长不能被4除

         {

             printf("no\n");

             continue;

         }

         len1/=;

         sort(a,a+n);

         memset(vis,,sizeof(vis));

         if(dfs(,,))  printf("yes\n");

         else printf("no\n");

     }

 }

相关文章