【深度搜索+剪枝】POJ2362-Square

从昨天晚上写到现在，一直在TLE，现在终于剪枝完成了_(:зゝ∠)_

【思路】

深搜：用这类型组合题目最基本的深搜，变量side记录当成已经组成了几条变，sl表示当前在组合的边已经有的长度。如果当前stick的长度与已有长度的和恰巧等于边长，则side+1，将sl清零；否则若小于边长，则sl+当前长度继续搜索，直到组成所有边为止。

剪枝：（1）如果木棒数目没有到达四根，则为no

　　（2）比较容易想到的一点，如果当前木棒总长不是4的整数倍，则为no

　　　（3）由于木棒不能这段，如果最长的木棒大于边长，则为no

　　　（4）由于越短的木棒灵活性越高，进行快排之后由大至小进行搜索。

　　　（5）为了避免重复搜索，我们默认组成同一边时，下一根取的木棒长度必定不大于当前根的木棒。故设置变量frm，即当前可取木棒长度的范围。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN=+;

 int stick[MAXN];

 int n,sum,m;

 bool visited[MAXN];

 bool dfs(int frm,int side,int sl)

 {

     if (==side) return(true);

     for (int i=frm;i>=;i--)

         if (!visited[i])

         {

             visited[i]=true;

             if (stick[i]+sl<sum)

             {

                 if (dfs(i-,side,sl+stick[i])) return true;

             }

             else

                 if (stick[i]+sl==sum)

                 {

                     if (dfs(m-,side+,)) return true;

                 }

             visited[i]=false;

         }

     return false;

 }

 int main()

 {

     scanf("%d",&n);

     for (int kase=;kase<n;kase++)

     {

         memset(visited,false,sizeof(visited));

         scanf("%d",&m);

         sum=;

         int max=-;

         for (int i=;i<m;i++)

         {

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

             sum+=stick[i];

             if (stick[i]>max) max=stick[i];

         }

         if (sum%!=||m<||max>sum/) cout<<"no"<<endl;

         else

         {

             sort(stick,stick+m);

             sum=sum/;

             if (dfs(m-,,)) cout<<"yes"<<endl;

             else cout<<"no"<<endl;

         }

     }

     return ;

 }

巴特西

【深度搜索+剪枝】POJ2362-Square

最新文章

热门文章