当前位置: 代码迷 >> 综合 >> HDU 1518 Square (DFS)
  详细解决方案

HDU 1518 Square (DFS)

热度:62   发布时间:2023-12-05 06:37:01.0
//题意不会度娘
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
using namespace std;
bool visit[25];
int a[25];
int sum;
int n,k;
bool cmp(int a,int b)
{return a>b;
}
bool DFS(int we,int rng,int edg)//we为已经拼好的边,rng为第几根,edg为下一根棍子剩余的长度 
{if(we==3)return true;//如果数据能进DFS循环,则说明拼好第三条边时必能拼好第四条边 for(int i=rng;i<n;i++)//边逐一相加 {if(visit[i])continue;//如果边已经使用过 visit[i]=true;//标为已经使用 if(a[i]==edg)//凑好一条边的剩余长度刚好为这条边的长度 {if(DFS(we+1,0,k))//边数加一,已用的边数变为一,剩余长度重新标为k	return true;}else if(a[i]<edg){if(DFS(we,i+1,edg-a[i]))//剩余的长度减去加上的a[i]长度 return true;}visit[i]=false;//都不符合则重新标为未使用 }	 return false;//无结果 
}
int main(int argc, char *argv[])
{int t;scanf("%d",&t);while(t--){sum=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];}k=sum/4; if(sum%4!=0)//如果边数总长度不能被4整除,则必定为no {printf("no\n");continue;}memset(visit,false,sizeof(visit));sort(a,a+n,cmp);if(DFS(0,0,k))printf("yes\n");elseprintf("no\n");}	return 0;
}
//start-ZJ
//2017/10/17/19:34