好贷网好贷款

hdu 1518

发布时间:2016-12-5 8:37:08 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1518",主要涉及到hdu 1518方面的内容,对于hdu 1518感兴趣的同学可以参考一下。

Square Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6818    Accepted Submission(s): 2214 Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?   Input The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.   Output For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".   Sample Input 3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5   Sample Output yes no yes   Source University of Waterloo Local Contest 2002.09.21 一道简单的dfs题,我已开始以为题意为可以不全部使用木棍,原来是,要全用上的.如果补全用上则需要每次去除若干个,然后就和木棍全部使用一样了. Accepted 1518 828MS 316K #include <iostream> using namespace std; bool visit[1200]; int val[1200]; int total; bool dfs(int index ,int n,int sum,int depth){ if (depth ==3) return true; if ( sum==total ) return dfs(0,n,0,depth+1); for ( int i=index;i<n; ++i ){ if ( visit[i] || val[i]+sum>total ) continue; visit[i]=true; if ( dfs(i+1,n,val[i]+sum,depth) ) return true; visit[i]=false; } return false; } int main() { int testnum ; int valnum; cin>>testnum; while ( testnum-- ){ total = 0; memset(visit,0,sizeof(visit)); cin>>valnum; for ( int i=0;i<valnum;++i ){ cin>>val[i]; total+=val[i]; } if ( total%4!=0 || valnum<4){ cout<<"no"<<endl; continue; } total/=4; if ( dfs(0,valnum,0,0) ){ cout<<"yes"<<endl; }else { cout<<"no"<<endl; } } return 0; } 用sort排序后: Accepted 1518 515MS 320K 1166 B C++ #include <iostream> #include <algorithm> using namespace std; bool visit[1200]; int val[1200]; int total; bool dfs(int index ,int n,int sum,int depth){ if (depth ==3) return true; if ( sum==total ) return dfs(0,n,0,depth+1); for ( int i=index;i<n; ++i ){ if ( visit[i] ) continue; if ( val[i]+sum>total ) return false; visit[i]=true; if ( dfs(i+1,n,val[i]+sum,depth) ) return true; visit[i]=false; } return false; } int main() { int testnum ; int valnum; cin>>testnum; while ( testnum-- ){ total = 0; memset(visit,0,sizeof(visit)); cin>>valnum; for ( int i=0;i<valnum;++i ){ cin>>val[i]; total+=val[i]; } if ( total%4!=0 || valnum<4){ cout<<"no"<<endl; continue; } total/=4; sort(val,val+valnum); if ( dfs(0,valnum,0,0) ){ cout<<"yes"<<endl; }else { cout<<"no"<<endl; } } return 0; }

上一篇:wubi安装ubuntu
下一篇:通过jconsole查看tomcat运行情况的配置方法——基于JDK1.5、Linux(Redhat5.5)、Tomcat6

相关文章

关键词: hdu 1518

相关评论