例题9.4Square
//DFS好像不能是void函数
//没什么好说的,上代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int totallen;
int m;//棒子个数
int stick[21];
bool visit[21];
bool cmp(int a,int b)
{
return a>b;
}
bool DFS(int sum,int number,int position)
{
if(number==3)
{
//cout<<"yes"<<endl;
return true;
}
// int sample=0;//不可能的重复边
for(int i=position;i<=m;i++)
{
int nsum=sum+stick[i];
// if(nsum>totallen/4||visit[i]||sample==stick[i])continue;
if(nsum>totallen/4||visit[i])continue;
visit[i]=true;
if(nsum==totallen/4)//凑成一条边
{
if(DFS(0,number+1,1))//下一条边从第一根棒开始测试
return true;
//else
//{
// sample=stick[i];//说明这根棒子不能在这种情况下被用
//}
}
else
{
if(DFS(nsum,number,i+1))
return true;
//else
//{
// sample=stick[i];
//}
}
visit[i]=false;
}
return false;
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>m;
totallen=0;
for(int j=1;j<=m;j++)
{
cin>>stick[j];
totallen+=stick[j];
}
memset(visit,false,sizeof(visit));
sort(stick+1,stick+1+m,cmp);
if(totallen%4!=0||stick[1]>totallen/4)
{
cout<<"no"<<endl;
}
else
{
if(DFS(0,0,1))//当前边的长度,拼好的边长数量,拼到第几个棒子
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}
}
//没什么好说的,上代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int totallen;
int m;//棒子个数
int stick[21];
bool visit[21];
bool cmp(int a,int b)
{
return a>b;
}
bool DFS(int sum,int number,int position)
{
if(number==3)
{
//cout<<"yes"<<endl;
return true;
}
// int sample=0;//不可能的重复边
for(int i=position;i<=m;i++)
{
int nsum=sum+stick[i];
// if(nsum>totallen/4||visit[i]||sample==stick[i])continue;
if(nsum>totallen/4||visit[i])continue;
visit[i]=true;
if(nsum==totallen/4)//凑成一条边
{
if(DFS(0,number+1,1))//下一条边从第一根棒开始测试
return true;
//else
//{
// sample=stick[i];//说明这根棒子不能在这种情况下被用
//}
}
else
{
if(DFS(nsum,number,i+1))
return true;
//else
//{
// sample=stick[i];
//}
}
visit[i]=false;
}
return false;
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>m;
totallen=0;
for(int j=1;j<=m;j++)
{
cin>>stick[j];
totallen+=stick[j];
}
memset(visit,false,sizeof(visit));
sort(stick+1,stick+1+m,cmp);
if(totallen%4!=0||stick[1]>totallen/4)
{
cout<<"no"<<endl;
}
else
{
if(DFS(0,0,1))//当前边的长度,拼好的边长数量,拼到第几个棒子
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}
}
全部评论
相关推荐
点赞 评论 收藏
分享
06-04 09:27
门头沟学院 Java 点赞 评论 收藏
分享