题解 P2383 【狗哥玩木棒】

· · 题解

蒟蒻的第一篇题解

直入正题， 我是纯dfs党不会什么二分，只会用点剪枝：

剪枝1：很容易想到，正方形的长度=所有木棍长度/4，若超过，return！

剪枝2：找到可以拼成的方法就回退。

剪枝3：有点难想，就是给木棍长度从大到小排序，因为大的活动性弱，可以决定大致范围，小的则用来补空缺，可以减掉无序时大多数的计算的浪费。

剪枝4：若正在拼一个新的边，放上去了第一根木棒，后面搜索又失败的话,那么无论怎样，这次搜索必然失败，因为所有木棒都无法与当前这根木棒进行匹配，那么这根木棒往后永远无法组成一条边，那么，return！

话不多说，上代码！ 码风奇异，大佬勿喷。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 1e18

int n,m,sum,a[1001],fail;bool b[1001],flag;//flag表示是否已找到  
bool cmp(int x,int y){return x>y;}
void dfs(int x,int z)//x为正在拼的木棒的长度，z表示已拼好的木棒长度 
{
    if(!flag)return;//剪枝2 
    if(x>sum)return;//剪枝1 
    if(x==sum)x-=sum,z+=1;
    if(z==4){cout<<"yes"<<endl;flag=0;//剪枝2 
    }
    for(int i=1;i<=m;i++){
        if(!b[i]){
            b[i]=1;//标记 
            dfs(x+a[i],z);
            b[i]=0;//回溯 
            if(x==0||x+a[i]==0)return;//剪枝4 
        }
    }
}
int main()
{
    cin>>n;
    while(n--)
    {
        sum=0;flag=1;
        memset(b,0,sizeof(b));//初始化 
        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>a[i];sum+=a[i];
        }
        sum/=4;
        sort(a+1,a+1+m,cmp);//剪枝3 
        dfs(0,0);
        if(flag)
        cout<<"no"<<endl;
    }
}

谢谢观看！