当前位置:编程学习 > C/C++ >>

hdu 1518 square

很是经典的深搜dfs,之前这题用了很长时间根本就没有思路,不知道如何下手,上网搜了一下别人的代码,感觉写的很好,而且思路很清晰,就自己写了;www.zzzyk.com
[cpp] 
#include<cstdio> 
#include<algorithm> 
#include<cmath> 
using namespace std; 
int num[25]; 
int sum=0,len; 
int n; 
bool ok; 
bool vis[25]; 
 void dfs(int s,int k,int cnt) 
{  int i; 
      if(s==len) 
      { 
         cnt++; 
         if(cnt==4) 
         {ok=1;return;} 
         s=0;k=0; 
      } 
      if(ok)return; 
      for(i=k;i<n;i++) 
      { 
       if(vis[i]==false) 
       { 
          if(s+num[i]>len) 
              continue; 
          vis[i]=true; 
          dfs(s+num[i],i,cnt); 
          vis[i]=false; 
       } 
      } 

int main() 

    int t; 
    scanf("%d",&t); 
    while(t--) 
    { 
       
        ok=0; 
            sum=0; 
            
       scanf("%d",&n); 
       int max=-10; 
     for(int i=0;i<n;i++) 
     { 
      scanf("%d",&num[i]); 
      if(max<num[i]) 
          max=num[i]; 
      sum+=num[i]; 
      vis[i]=false; 
     } 
       
     if(n<4) 
     { printf("no\n");continue;} 
     if(sum%4||sum/4<max) 
     { 
      printf("no\n");continue; 
     }else 
     { 
      len=sum/4; 
     dfs(0,0,0); 
      if(ok) 
          printf("yes\n"); 
      else 
          printf("no\n"); 
     } 
    } 
 return 0; 

///* 
//10 
//6 3 4 4 3 1 1 
//20 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 
//*/ 
  作者:Java_beginer1
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,