首页 > 代码库 > POJ 2362

POJ 2362

2024-07-16 15:49:23   221人阅读

知识点：dfs（深度优先搜索）

题解：基本的dfs搜索判断可行性问题。一般的dfs搜索，如果不加剪枝，复杂度是指数级的，所以必须要能发掘出优秀的剪枝条件；

在本题中，一般有如下剪枝：

①：所有线段的长度之和必须为4的倍数；
②：搜索之前，把所有线段按从大到小排序，因为长度越长，在拼凑时的灵活度就越低；
③：当能拼凑出3根等长的线段时，第四根就无须再搜了；
④：当用某一条线段无法得出可行解时，和它等长的，一样不可以；

有了以上四个剪枝条件，这题就可以过了；

add：这题理解之后可以去看看poj 1011，那题是本题的加强版，所以光凭以上4个剪枝还是无法通过，大家要接着发掘剪枝条件；

 

 

 
 1 #include <iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<vector> 7 #include<map> 8 #include<string> 9 #include<cmath>10 #include<queue>11 #define N 100512 #define M 1013 #define MAXN 100000514 #define mod 100000000015 #define ll long long16 using namespace std;17 18 int n,T;19 int a[N];20 int flag;21 int sum;22 int ma;23 int l;24 int vis[N];25 26 bool cmp(int x,int y)27 {28     return x>y;29 }30 31 int DFS(int done,int left,int cur)32 {33   //  printf(" done=%d left=%d cur=%d\n",done,left,cur);34     if(left==0){35         if(done==3) return 1;36         else{37             if(DFS(done+1,l,1)==1) return 1;38             else return 0;39         }40     }41     else{42         for(int i=cur;i<=n;i++){43             if(vis[i]==1) continue;44             if(a[i]>left) continue;45             vis[i]=1;46             if(DFS(done,left-a[i],i)==1) return 1;47             else{48                 vis[i]=0;49                 int j=i+1;50                 while(j<=n && a[j]==a[i]){51                     j++;52                 }53                 i=j-1;54             }55         }56         return 0;57     }58 }59 60 int main()61 {62     int i,j,k;63   //  freopen("data.txt","r",stdin);64     scanf("%d",&T);65     //while(scanf("%d",&n)!=EOF)66     while(T--)67    // for(cnt=1;cnt<=T;cnt++)68     {69         scanf("%d",&n);70         memset(vis,0,sizeof(vis));71         sum=flag=0;ma=0;72         for(i=1;i<=n;i++){73             scanf("%d",&a[i]);74             sum+=a[i];75             ma=max(a[i],ma);76         }77         if(sum%4!=0 || ma>sum/4){78             printf("no\n");79             continue;80         }81         l=sum/4;82         sort(a+1,a+1+n,cmp);83         vis[1]=1;84         if(DFS(0,l-a[1],1)==1)85             printf("yes\n");86         else87             printf("no\n");88 89     }90 91     return 0;92 }
 






























        

            
                
                  
                
                

                    联系

                    我们