Posted on 2008-10-14 19:36
Hero 閱讀(111)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //3400 Accepted 312K 250MS G++ 1584B PKU
2
3 // 無語--題目意思一直理解錯
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 12 ;
10
11 struct NODE
12 {
13 int num ;
14 int weight ;
15 int value ;
16 };
17 struct NODE node[size] ;
18
19 int weight[2] ;
20 int value[2] ;
21
22 int now ;
23
24 int flag[size] ;
25
26 int inn, ind ;
27 int best ;
28 int sum ;
29
30 void input()
31 {
32 sum = 0 ;
33 for( int i=1; i<=inn; i++ )
34 {
35 node[i].num = i ;
36 scanf( "%d %d", &node[i].weight, &node[i].value ) ;
37 sum += node[i].value ;
38 }
39 }
40
41 void DFS( int dep, int tdep, int stone, int bunk, int tsum )
42 {
43 if( value[1] + tsum <= best ) return ;
44
45 flag[stone] = 1 ; weight[bunk] += node[stone].weight ; value[bunk] += node[stone].value ;
46
47 if( dep == tdep )
48 {
49 //printf( "best==%d value[1]==%d\n", best, value[1] ) ;
50 best = best > value[1] ? best : value[1] ;
51 }
52
53 for( int i=1; i<=inn; i++ ) if( 0 == flag[i] )
54 {
55 if( weight[bunk]-weight[1-bunk] > ind )
56 DFS( dep+1, tdep, i, 1-bunk, tsum-node[stone].value ) ;
57
58 else
59 DFS( dep+1, tdep, i, bunk, tsum-node[stone].value ) ;
60 }
61
62 flag[stone] = 0 ; weight[bunk] -= node[stone].weight ; value[bunk] -= node[stone].value ;
63 }
64
65 void process()
66 {
67 best = -1 ;
68
69 for( int i=1; i<=inn; i++ )
70 {
71 memset( flag, 0, sizeof(flag) ) ;
72 weight[0] = weight[1] = 0 ; value[0] = value[1] = 0 ;
73
74 DFS( 1, inn, i, 0, sum ) ;
75
76 //DFS( 1, inn, i, 0, node[i].weight, node[i].value, 0, 0 ) ;
77 }
78 }
79
80 void output()
81 {
82 printf( "%d\n", best ) ;
83 }
84
85 int main()
86 {
87 while( scanf( "%d %d", &inn, &ind ) != EOF )
88 {
89 input() ;
90
91 process() ;
92
93 output() ;
94 }
95
96 return 0 ;
97 }