优化剪枝搜索——牛客多校第二场F

以你之姓@ 2023-10-11 09:13 6阅读 0赞

试了很多种爆搜和剪枝，最后发现还是状压的比较好用

#include <bits/stdc++.h>
    using namespace std;
    // #define IO
    #define fi first
    #define se second
    #define pb push_back
    #define mk make_pair
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    #define rep(i,s,t) for(int i=s;i<t;i++)
    #define REP(i,s,t) for(int i=s;i<=t;i++)
    #define DOW(i,s,t) for(int i=s;i>=t;i--)
    #define dow(i,s,t) for(int i=s;i>t;i--)
    #define clr(a,b) memset(a,b,sizeof(a))
    #define debug(x) cout<<#x<<' '<<x<<endl
     
    typedef long long ll;
    typedef pair<int,int>pii;
    inline int lowbit(int x){ return x&(-x); }
    template<typename T>
    inline void read(T&x){
        x=0;int f=1;char ch=getchar();
        while(ch<'0' ||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); }
        while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
        x*=f;
    }
    const int N = 110;
    ll g[N][N];
    ll n,ans;
     
    void dfs(int mask,int num,int pre,ll preans){
        if(num<<1==n){
            ans=max(ans,preans);return;
        }
        if(n-1-pre+num<n/2)return;       //表示即使是接下来的所有数都选，也不符合条件(集合不能够选够n/2个元素)，就直接返回(最优性剪枝)
        for(int i=pre+1;i<n;i++){
            ll nowans=preans;
            rep(j,0,n){
                if(mask&(1<<j))nowans-=g[i][j];
                else nowans+=g[i][j];
            }
            dfs(mask|(1<<i),num+1,i,nowans);
        }
    }
    int main(){
        cin>>n;n<<=1;
        rep(i,0,n) rep(j,0,n) read(g[i][j]);
        ll nowans=0;        //现在将第一个点放到另一个集合中
        rep(i,0,n)nowans+=g[0][i];
        dfs((1<<0),1,0,nowans);
        printf("%lld\n",ans);
        return 0;
    }

然后还有一种不同思路的搜索，一开始两个集合都为空，然后往两个集合里填元素，这样会少很多冗余的搜索

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll n,vis[30],mp[30][30],ans;
    
    
    int s1[30],s2[30],top1,top2;
    void dfs(int pos,ll now){
        if(pos>2*n){
            ans=max(ans,now);
            return;
        }
        if(top1<n){
            s1[++top1]=pos;
            ll nxt=now;
            for(int i=1;i<=top2;i++)
                nxt+=mp[pos][s2[i]];
            dfs(pos+1,nxt);
            top1--;
        }
        if(top2<n){
            s2[++top2]=pos;
            ll nxt=now;
            for(int i=1;i<=top1;i++)
                nxt+=mp[pos][s1[i]];
            dfs(pos+1,nxt);
            top2--;
        }
    }
    
    int main(){
        cin>>n;
        for(int i=1;i<=2*n;i++) 
            for(int j=1;j<=2*n;j++)
                scanf("%d",&mp[i][j]);
        ans=0;
        dfs(1,0);
        cout<<ans<<endl;
    }
    /*
    (28,14)=
    */

转载于:https://www.cnblogs.com/zsben991126/p/11287855.html