HDU 1518 Square （DFS）

迷南。 2022-06-07 09:50 120阅读 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");
    		else
    			printf("no\n");
    	}	
    	return 0;
    }

//start-ZJ

//2017/10/17/19:34