Square(强大的剪枝)
Square(强大的剪枝)
1944864971 发表于2年前
Square(强大的剪枝)
  • 发表于 2年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2410

/*
题意;
给出一定数量的棍子用这些棍子组成一个正方形
要求把这些棍子全部用完
能组成正方形输出yes否则输出no

分析;

正方形的边长都相同
即是找出四条边长一样的边

第一 : 周长必须是4的倍数
第二 : 最长的木棍必须小于等于边长
第三:木棍重大到小排序 找边是从大向小的开始找,不必每次都从头找一遍

*/

include

include

include

using namespace std;
int stick[25];
int vis[25];
int op=0,bianZhang ;
int m;
bool myCmp(int a,int b)
{
return a>b;
}
void dfs(int cur,int sum,int start)
{
if(cur==3)
{
op=1;
return ;
}
if(op)return ;
for(int i=start; i<m; i++)
{
if(vis[i]==1)continue;
if(sum+stick[i]==bianZhang)
{
if(op)return;//如果没有 超时
vis[i]=1;
dfs(cur+1,0,0);//找到一条边 准备找下一条
vis[i]=0;
}
else if(sum+stick[i]<bianZhang)//还没有组成一条边
{
if(op)return;//如果没有 超时
vis[i]=1;
dfs(cur,sum+stick[i],i);
vis[i]=0;
}
}
return ;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
memset(stick,0,sizeof(stick));
memset(vis,0,sizeof(vis));
op=0;
int sum=0;
for(int i=0; i<m; i++)
{
scanf("%d",&stick[i]);
sum+=stick[i];
}
if(sum%4!=0||m<4)
{
printf("no\n");
continue;
}
sort(stick,stick+m,myCmp);
bianZhang=sum/4;
if(stick[0]>bianZhang)
{
printf("no\n");
continue;
}
dfs(0,0,0);
if(op )
printf("yes\n");
else
printf("no\n");
}
return 0;
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: