可行性剪枝 lydsy begin 1263 Square

观察题目[1]很容易发现应该使用深度优先搜索。但是情况很多,数据量较大,很容易超时。我进行了初步的剪枝:

  1. 总长必须是4的倍数
  2. 当前边不能超过总周长除以4

得代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <set>
  
#define clr(x) memset(x,0,sizeof(x))
#define fort(i,n) for(int i=0;i<(n);i++)
#define forf(i,n) for(int i=(n);i>=0;i--)
#define timer() ((ldouble)clock()/CLOCKS_PER_SEC)
#define valid(x,y,m,n) ((x)>=0&&(x)<(m)&&(y)>=0&&y<=(n))
#define bitat(num,d) ((num>>d)&1)
#define synf() ios::sync_with_stdio(false),cin.tie(0)
#define debug(n) {cerr<<#n<<"="<<n<<endl;}
  
using namespace std;
typedef long long lint;
typedef long double ldouble;
template<typename T> T gcd(T a, T b){return a?gcd(b%a,a):b;}
  
int l[25],m,a;
bool used[25];
  
bool dfs(int stage,int curlen){
    if(stage==4){
        return true;
    }
    if(curlen==a){
        return dfs(stage+1,0);
    }
    fort(i,m){
        if(!used[i]){
            if(curlen+l[i]<=a){
                used[i]=true;
                if(dfs(stage,curlen+l[i])){
                    return true;
                }
                used[i]=false;
            }
        }
    }
    return false;
}
  
int main(){
    int tot,sum;
    cin>>tot;
    while(tot--){
        cin>>m;
        sum=0;
        fort(i,m){
            cin>>l[i];
            sum+=l[i];
        }
        if(sum%4==0){
            a=sum/4;
            clr(used);
            if(dfs(0,0)){
                cout<<"yes"<<endl;
            }else{
                cout<<"no"<<endl;
            }
        }else{
            cout<<"no"<<endl;
        }
    }
}

结果还是超时了。

再仔细思考一下,对于每一条边,假如说由4根木棍组成,那么有A44A_4^4种深搜情况,全部都浪费了。对于这个情况,进行剪枝!规定对每一条边只能有序的选择,排除掉多余的情况。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <set>
   
#define clr(x) memset(x,0,sizeof(x))
#define fort(i,n) for(int i=0;i<(n);i++)
#define forf(i,n) for(int i=(n);i>=0;i--)
#define timer() ((ldouble)clock()/CLOCKS_PER_SEC)
#define valid(x,y,m,n) ((x)>=0&&(x)<(m)&&(y)>=0&&y<=(n))
#define bitat(num,d) ((num>>d)&1)
#define synf() ios::sync_with_stdio(false),cin.tie(0)
#define debug(n) {cerr<<#n<<"="<<n<<endl;}
   
using namespace std;
typedef long long lint;
typedef long double ldouble;
template<typename T> T gcd(T a, T b){return a?gcd(b%a,a):b;}
   
int l[25],m,a;
bool used[25];
  
bool dfs(int stage,int curlen,int least){
    if(stage==4){
        return true;
    }
    if(curlen==a){
        return dfs(stage+1,0,0);
    }
    for(int i=least;i<m;i++){
        if(!used[i]){
            if(curlen+l[i]<=a){
                used[i]=true;
                if(dfs(stage,curlen+l[i],i)){
                    return true;
                }
                used[i]=false;
            }
        }
    }
    return false;
}
int main(){
    int tot,sum;
    cin>>tot;
    while(tot--){
        cin>>m;
        sum=0;
        fort(i,m){
            cin>>l[i];
            sum+=l[i];
        }
        sort(l,l+m);//这里其实多余了,只要按照边的顺序来选择就可以了。
        if(sum%4==0){
            a=sum/4;
            clr(used);
            if(dfs(0,0,0)){
                cout<<"yes"<<endl;
            }else{
                cout<<"no"<<endl;
            }
        }else{
            cout<<"no"<<endl;
        }
    }
}

到这里就已经AC了。其实可以更进一步优化。四条边深搜的顺序不同,导致多了A441=23A^4_4-1=23种情况。这样其实也只是优化常数而已,但是能更进一步加速。

总结一下,搜索过程可以看作是对一棵树的遍历。在很多情况下,并不是搜索树中的所有枝条都能通向我们需要的结果,很多的枝条实际上只是一些死胡同,或者一模一样的情况。如果我们能够在刚刚进入这样的死胡同的时候,就能够判断出来并立即剪枝,程序的效率往往会得到提高。而所谓可行性剪枝,正是基于这样一种考虑。


  1. http://begin.lydsy.com/JudgeOnline/problem.php?id=1263&csrf=dd6f96fdfe8353954310da6d40417749

avatar
Kerry Su