注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1518  

2012-08-13 15:24:10|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=1518

这是一道dfs,开始不怎么好下手,后来看了提示后,看了dfs的参数提示来能写出来

 /*
 * fudq.cpp
 *
 *  Created on: 2012-08-13
 */
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
using namespace std;
int n,s,a[22],t[22];

int dfs(int sta,int len,int step)//sta表示当前点位置,len表示边长,step表示边数
{
 if(len==s)
 {
  if(step==3)//只要找到两条就够了,因为剩下的既要满足相加为两条边的和,而且两条边都不能大于边长
   return 1;
  return dfs(0,0,step+1);
 }
 for(int i=sta;i<n;i++)
 {
  if(!t[i] && len+a[i]<=s)
  {
   t[i]=1;
   if(dfs(i+1,len+a[i],step))
    return 1;
   t[i]=0;
  }
 }
 return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int T,i,m_l;
    scanf("%d",&T);
    while(T--)
    {
     scanf("%d",&n);
     for(i=0,s=0,m_l=0;i<n;i++)
     {
      scanf("%d",&a[i]);
      s+=a[i];
      if(a[i]>m_l)
       m_l=a[i];
     }
     if(s%4!=0 || m_l>s/4)
     {
      printf("no\n");
      continue;
     }
     memset(t,0,sizeof(t));
     s/=4;
     if(dfs(0,0,1))
      printf("yes\n");
     else
      printf("no\n");
    }
    return 0;
}


  评论这张
 
阅读(494)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018