博客

好久没做深搜了，上午优哉游哉的想自己的为啥超时要咋剪枝呢，得到下午就考生态期中的噩耗直接跑出去了~。~

说题意：一个月前学弟问过，简单看过代码，都忘了，(⊙﹏⊙)b 既然是深搜，函数参数里面一定是带着需要用的量的==

对于这个题来说，带着的三个参数分别是：当前这条边的长度，凑完的边数，从第几个木棍开始找

看这个代码就在纠结哪里体现出现在遍历的这个木棍用还是不用：for循环啊

代码：

/***********
hdu1518
2015.12.14
1045MS 1564K 1231 B
***********/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t,m,num[22],sum,target;
bool vis[22];
bool cmp(int a,int b)
{
    return a<b;
}
bool dfs(int sum,int cnt,int k)
{
    if(cnt==3) return true;
    for(int i=k;i>=1;i--)
    {
        if(vis[i]==0)
        {
            vis[i]=1;//递归的精髓就是回溯啊~~这咋能写错
            if(sum+num[i]==target)
            {
                if(dfs(0,cnt+1,m)) return true;
            }
            else if(sum+num[i]<target)
            {
                if(dfs(sum+num[i],cnt,i-1)) return true;//是从下一个开始找啊 跟之前k是几没关系啊
            }
            vis[i]=0;///咋想的啊 还能写成=1
        }
    }
    return false;
}
int main()
{
   // freopen("cin.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&m);
        sum=0;
        for(int i=1;i<=m;i++) {
            scanf("%d",&num[i]);
            sum+=num[i];
        }
        memset(vis,0,sizeof(vis));
        target=sum/4;
        if(m<=3||sum%4!=0) puts("no");
        else if(dfs(0,0,m)) puts("yes");
        else puts("no");
    }
    return 0;
}