Posted on 2009-07-10 14:55
Hero 閱讀(216)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
代碼如詩(shī)－－ACM
1 //HLOJ 1037 Accepted 1437 136 676 C++
2
3 //深度優(yōu)先搜索
4
5 #include <iostream>
6
7 using namespace std ;
8
9 const int size = 100 ;
10
11 int data[size] ;
12
13 int inn, inc ;
14 bool OK = false ;
15
16 void DFS( int deep, int val, int remain )
17 {
18 if( val == inc ) OK = true ;
19
20 if( deep > inn ) return ;
21
22 if( val + remain < inc ) return ;
23
24 if( OK ) return ;
25
26 DFS( deep+1, val+data[deep], remain-data[deep]) ;
27 DFS( deep+1, val, remain ) ;
28 }
29
30 int main()
31 {
32 while( cin >> inn >> inc )
33 {
34 int sum = 0 ;
35 OK = false ;
36
37 for( int i=1; i<=inn; i++ )
38 {
39 cin >> data[i] ;
40 sum = sum + data[i] ;
41 }
42
43
44 DFS( 1, 0, sum ) ;
45
46 if( OK )
47 printf( "Yes\n" ) ;
48 else
49 printf( "No\n" ) ;
50 }
51 return 0 ;
52 }