http://poj.org/problem?id=2362

dfs+多重剪枝

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int num[20];
int v[20],n;
int cmp(const int& a,const int& b)
{
    return a>b;
}
int dfs(int s_len,int sum,int stick_num,int start)
{
     if(stick_num==3) return 1;//剪枝2
    // if(start==n) return 0;
     for(int i=start;i<n;i++)
     {
        if(!v[i])
        {
           if(sum+num[i]==s_len)
           {
              v[i]=1;
              if(dfs(s_len,0,stick_num+1,0)) return 1;
              v[i]=0;
			/*  return 0;*/
           }
           if(sum+num[i]<s_len)
           {
             v[i]=1;
             if(dfs(s_len,sum+num[i],stick_num,i+1)) return 1;
	     v[i]=0;
	     if(sum==0)//剪枝3
	        return 0;
           }
       }
	 }
     return 0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int sum=0,single;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&num[i]);
            v[i]=0;
            sum+=num[i];
        }
        sort(num,num+n,cmp);
	//	printf("%d\n",num[0]);
        if(n<4||sum%4!=0||sum/4<num[0])//剪枝1
             printf("no\n");
        else
	{
        single=sum/4;
        if(dfs(single,0,0,0))
            printf("yes\n");
        else
             printf("no\n");
	}
    }
  return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation