dfs+剪枝 poj1011

小咪咪 2022-08-03 16:54 193阅读 0赞

大致题意：给定一堆不定长度的小棒子，问他们能否构成一个正方形。

思路：对所有的棒子求和sum之后除以4，得到边长side，问题就转换为求这些棒子能否拼接成4个长度为side的长棒子。

有些地方可以剪枝：

1，棒子的个数小于4或者sum不能整除4.

2，边长side要大于等于棒子中最长的一根，因为棒子不能弄断

3，当满足前两者的时候，只要拼接成了三条边就可以了

4，将所有棒子降序排列之后，每次搜索的时候，从当前用过的棒子开始搜索，因为若当前棒子的前面棒子没有用到的时候，那搜索同一条边的时候这些都用不到了，没有必要每次都从头开始搜索。

从最长的棒子开始dfs

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <string>
    using namespace std;
    
    #define mem(a) memset(a,0,sizeof(a))
    
    int sum,side,n;//总长度,边长,个数
    int vis[305];//判断是否已经用过
    int s[305];//存储棒子的长度
    int ans;
    
    bool cmp(int a,int b)
    {
        return a>b;//降序
        //return a<b 升序
    }
    
    void dfs(int num,int len,int a)
    {//num当前已经拼接的正方形的边数，
     //len正在拼接的边的长度,len<=side,
     //a每次搜索起点
    
       if(num==3)
       {
           ans=1;return;
       }
       for(int i = a ; i < n ; i++)
       {
           if(vis[i])continue;//已经用过了
           if(len+s[i]<side)
           {
               vis[i]=1;
               dfs(num,len+s[i],i);//i作为在此搜索的起点
           }
           else if(len+s[i]==side)
           {
               vis[i]=1;
               dfs(num+1,0,0);//当前边拼接完成
           }
           vis[i]=0;     //若是不成功，则需要再次搜索，回溯
       }
    }
    
    int main()
    {
       int t;
       scanf("%d",&t);
       while(t--)
       {
           scanf("%d",&n);
           sum=0;
           for(int i = 0 ; i < n ; i++)
           {
               scanf("%d",&s[i]);
               sum+=s[i];
           }
           sort(s,s+n,cmp);   //默认的是升序
           if(sum%4!=0||n<4)   //剪枝1
           {
               printf("no\n");
               continue;
           }
           side=sum/4;
           if(s[0]>side)     //剪枝2
           {
               printf("no\n");
               continue;
           }
           mem(vis);
           ans=0;
           dfs(0,0,0);  //从最长的开始搜索
           if(ans==0) printf("no\n");
           else if(ans==1)printf("yes\n");
       }
       return 0;
    }