题解 P2383 【狗哥玩木棒】

Arse、三千体 · 2019-09-21 14:33:44 · 题解

比较简单的明显的dfs

但是不加剪枝必定超时

思路：对于每组数据，计算出每边应有长度（题目要求所有边都用），若每条边的长度都能拼出，则yes，否则no

上代码

#include<bits/stdc++.h>//万能头不解释
using namespace std;
int t,n,an,ans=4;//分别为：数据数，木棒数，每边应有长度，剩余未拼成的边数
bool booka[20];//标记木棒是否使用过
bool flag;//是否拼成
int a[20];//木棒长度
void dfs(int sum)
{
    if(ans==0)//若应拼边数为零，则已拼好
    {
        flag=true;
        return;//打上已完成的标记
    }

    if(!flag)//若没有完成
    {
        for(int i=0;i<n;i++)
        {
            if(sum+a[i]==an&&!booka[i])/*如果此数没有用到且当前长度加上已拼好的长度等于边长，即又拼好了一边，则应拼边数自减，打上标记，已拼好的长度回到0，进行下一边*/
            {
                ans--;
                booka[i]=true;
                dfs(0);
                if(flag) return;/*剪枝，若已拼好，则不进行之后的计算（后同）*/
                ans++; //回溯
                booka[i]=false;
            }
            if(sum+a[i]>an) return;/*排序的作用：若现在边长+此边长大于应有边长，则这个不可能，后续数均大于等于此数，所以后面也不可能，直接返回上层*/
            else if(!booka[i])//非特殊条件，进行下一次操作
            {
                booka[i]=true;
                dfs(sum+a[i]);
                if(flag) return;
                booka[i]=false;
            }
        }
    }
    else return;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int maxn=0;//记录木棒总长
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            booka[i]=false;//边读入边赋值，相当于循环外加memset
            maxn+=a[i];
        }
        sort(a+0,a+n-1);//先排序，dfs剪枝用
        if(maxn%4!=0)
        {
            cout<<"no"<<endl;
            continue;
        }/*因为题目要求全部用到，所以若总长不是4的倍数，则不可能全用完且拼成*/
        an=maxn/4;//每边应有长度
        for(int i=0;i<n;i++) if(a[i]==an) ans--;/*若有某一边长等于应有边长，则需要拼的边数减一，即已经拼好一根*/
        if(ans==0)//若应拼的边数为零，则已经拼好，输出
        {
            cout<<"yes"<<endl;
            continue;
        }
        dfs(0);//dfs，参数是当前拼的边的长度
        if(flag)  cout<<"yes"<<endl;//输出
        else cout<<"no"<<endl;
        ans=4;//未拼好边数恢复4
        flag=false;//恢复标记为未拼成
    }
}

马上考试了，祝大家ak！！！

卑微的我请求通过