Square 北大POJ2362 深度优先搜索相关 计算机考研机试指南整理
程序员文章站
2022-07-16 09:39:11
...
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 25;
int sticks[MAXN];
bool visit[MAXN];
int m;
int side;
bool Compare(int x,int y){
return x>y;
}
bool DFS(int sum,int number,int position){ //sum 当前拼凑的木棍长度,number 已拼凑出的边长,position 当前木棍的编号
if(number == 3){
return true;
}
int sample = 0 ; //记录失败的木棍长度,下次再遇到直接跳过。
for(int i = position; i < m ; i++){ //从上一位置接着寻找
if(visit[i] || sum +sticks[i] > side || sticks[i] == sample){//在凑成一条边的路径中
continue;
}
visit[i] = true;
if(sum + sticks[i] == side){ //一条边已经凑齐
if(DFS(0,number+1,0)){ //当一条边已经凑齐了之后,重新开始另一条边要从头开始查找可以使用的木棍
return true;
}else {
sample = sticks[i];
}
} else {
if(DFS(sum + sticks[i],number,i+1)){ //一条边没有凑齐,继续凑下一个木棍
return true;
}else {
sample = sticks[i];
}
}
visit[i] = false;
}
return false;
}
int main()
{
int n ;cin>>n;
while(n--){
cin>>m;
int length =0;
for(int i = 0 ; i < m; i++){
cin>>sticks[i];
length += sticks[i];
}
if(length % 4 != 0){
cout<<"no"<<endl;
continue;
}
side = length/4;
sort(sticks,sticks + m,Compare);
if(sticks[0] > side){
cout<<"no"<<endl;
continue;
}
memset(visit,false,sizeof(visit));
if(DFS(0,0,0)){
cout<<"yes"<<endl;
}else {
cout<<"no"<<endl;
}
}
return 0;
}
上一篇: 斐波那契数列
下一篇: P1855 榨取kkksc03