题解 P2383 【狗哥玩木棒】

睿屿青衫 · 2017-09-10 16:53:05 · 题解

本来不太会，搜索一直是我的软肋，然后看了看楼下的题解，补充一下，为新手解答

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 10010
using namespace std;
int n,m,flag,q[maxn],p[maxn],tot,y[maxn];
void dfs(int x)
{
    if(flag) return;//如果为1了，能输出yes，不需要继续搜了，退出 
    if(x==m+1)//到了这一层，就意味着所有的木棍都用完了 
    {
        flag=1;//如果可以拼成，标记为1，退出 
        return;
    }
    for(int i=1;i<=4;++i)
     {
         if(p[x]<=y[i])//之前不太懂，想了想，这跟木棒比这条边剩下的长度小，那么就能放了 
         {
             y[i]-=p[x];//放上一根，该边剩余长度减去 
             dfs(x+1);//搜下一根 
             y[i]+=p[x];//回溯，上一步 
         }
     }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int o=1;o<=n;++o)
     {
         memset(q,0,sizeof(q));
         memset(p,0,sizeof(p));
         flag=0;tot=0;//因为是多组数据，所以清零 
         cin>>m;
         for(int i=1;i<=m;++i)
          {
              cin>>p[i];
              tot+=p[i];//把木棒总长度加起来 
          }
        if(tot%4!=0)//如果总长度除4不是整数，别浪费时间了 
         {
             printf("no\n");
             continue;
         }
        sort(p+1,p+m+1);//加一个排序，省时间（省的乱找） 
        for(int i=1;i<=4;++i) y[i]=tot/4;//每一个边都是四分之一 
        dfs(1);//从第一根开始找 
        if(flag) printf("yes\n");//标记，若为1，yes 
         else printf("no\n");
     }
    return 0;
}