【POJ 2362】【搜索】Square

2016-12-02 12:52:27来源:网络收集作者:Alex人点击

这次和学姐做的搜索专题,被虐的不要不要。


这题是赛后补的。参考了学姐代码,感觉剪枝是个技术活。


#include "iostream"
#include "algorithm"
using namespace std;
int a[100],vis[100];
int n,len,flag;
void dfs(int num,int ans,int k);
int main(int argc, char const *argv[])
{
int t;
scanf("%d",&t);
while(t--)
{
int sum=0;
scanf("%d",&n);
for (int i = 0; i < n; ++i)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%4==0)
{
sort(a,a+n);
memset(vis,0,sizeof(vis));
flag=0;
len=sum/4;
dfs(0,0,0);
flag?printf("yes/n"):printf("no/n");
}
printf("no/n");
}
return 0;
}
void dfs(int num,int ans,int k)
{
if(num==3)//如果能被整除,而且达到三根,那么第四根肯定可以形成,所以剪枝
{
flag=1;return;
}
if(ans==len)
{
num++;
k=0;
ans=0;
}
for (int i = k; i < n; ++i)
{
if(!vis[i] && ans+a[i]<=len)
{
vis[i]=1;
dfs(num,ans+a[i],i+1);
if(flag)
return;
vis[i]=0;
}
}
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台