题解 P2383 【狗哥玩木棒】

xgwpp6710 · 2020-01-15 20:45:07 · 题解

第一次写题解，写得不好请谅解

总的思路就是DFS

详细思路在程序里

#include<bits/stdc++.h>
using namespace std;
int leng[1015],n,m,bc;
bool vis[1015]={0},flag=0;//bc=边长 
void dfs(int k,int s)//目前在拼第k条边，这条边还剩s没拼 
{
    if(k==4)//前三条边都拼好了，第四条一定拼的好
    {
        flag=1;//有拼的方法
        return;
    }
    for(int i=1;i<=m;i++)//枚举每一条边 
    {
        if(!vis[i]&&leng[i]<s)
        {
            vis[i]=1;//这一条取过了
            dfs(k,s-leng[i]);//取这一条 
            vis[i]=0;
        }
        else if(!vis[i]&&leng[i]==s)
        {
            vis[i]=1;//这一条取过了
            dfs(k+1,bc);
            vis[i]=0;
        }
        else continue;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        bc=0;
        cin>>m;
        for(int j=1;j<=m;j++)
        {
            cin>>leng[j];
            bc+=leng[j];
        }
        if(bc%4!=0) cout<<"no\n";//总长度不是4的倍数，直接结束
        else
        {
            bc/=4;
            flag=0;
            dfs(1,bc);
            if(flag) cout<<"yes\n";
            else cout<<"no\n";
        }
    }
    return 0;
}

这是我的最初代码，然而样例2 TLE了 于是我加了剪枝

#include<bits/stdc++.h>
using namespace std;
int leng[1015],n,m,bc;
bool vis[1015]={0},flag=0;//bc=边长 
void dfs(int k,int s,int pre)//目前在拼第k条边，这条边还剩s没拼 
{
    if(k==4)
    {
        flag=1;
        return;
    }
    for(int i=pre;i<=m;i++)//枚举每一条边 
    {
        if(!vis[i]&&leng[i]<s)
        {
            vis[i]=1;
            dfs(k,s-leng[i],i+1);//取这一条 
            vis[i]=0;
        }
        else if(!vis[i]&&leng[i]==s)
        {
            vis[i]=1;
            dfs(k+1,bc,1);
            vis[i]=0;
        }
        else continue;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        bc=0;
        cin>>m;
        for(int j=1;j<=m;j++)
        {
            cin>>leng[j];
            bc+=leng[j];
        }
        if(bc%4!=0) cout<<"no\n";
        else
        {
            bc/=4;
            flag=0;
            dfs(1,bc,1);
            if(flag) cout<<"yes\n";
            else cout<<"no\n";
        }
    }
    return 0;
}

加了pre的剪枝，减少枚举 然而还是TLE 进一步优化

#include<bits/stdc++.h>
using namespace std;
int leng[1015],n,m,bc;
bool vis[1015]={0},flag=0;//bc=边长 
bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int k,int s,int pre)//目前在拼第k条边，这条边还剩s没拼 
{
    if(k==4)
    {
        flag=1;
        return;
    }
    if(!flag)
    {
        for(int i=1;i<=m;i++)//枚举每一条边 
        {
            if(!vis[i]&&leng[i]<s)
            {
                vis[i]=1;
                dfs(k,s-leng[i],i+1);//取这一条 
                vis[i]=0;
            }
            else if(!vis[i]&&leng[i]==s)
            {
                vis[i]=1;
                dfs(k+1,bc,1);
                vis[i]=0;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        bc=0;
        cin>>m;
        for(int j=1;j<=m;j++)
        {
            cin>>leng[j];
            bc+=leng[j];
        }
        if(bc%4!=0) cout<<"no\n";
        else if(m<4) cout<<"no\n";
        else
        {
            bc/=4;
            flag=0;
            sort(leng,leng+m,cmp);
            dfs(1,bc,1);
            if(flag) cout<<"yes\n";
            else cout<<"no\n";
        }
    }
    return 0;
}

又增加了把所有长度倒序排列的优化，这样又可以减少枚举次数，终于AC了 其实还有如果一条边的长度比（正方形的）边长长的话，直接跳出这一个剪枝，但既然AC了，我就懒得写了