Nâng cấp PC - NDDCoder

Fork

#include <iostream>
using namespace std;
int n,m,l,bestPrice;
int Market[25], Combo[35][35], ComboPrice[35], needItem[35], Visit[35];
void Try(int i, int price){
    if(price>bestPrice) return;
    if(i>l){
        if(price<bestPrice) bestPrice=price;
        return;
    }
    if(Visit[needItem[i]]) Try(i+1,price);
    else{
        Visit[needItem[i]]++;
        Try(i,price+Market[needItem[i]]);
        Visit[needItem[i]]--;        ////Reset Visit

for(int k=1; k<=m; k++){
            for(int h=1; h<=Combo[k][0]; h++){
                if(Combo[k][h]==needItem[i]){
                    for(int t=1; t<=Combo[k][0]; t++) Visit[Combo[k][t]]++;
                    Try(i+1,price+ComboPrice[k]);
                    for(int t=1; t<=Combo[k][0]; t++) Visit[Combo[k][t]]--; ////Reset Visit
                }
            }
        }
    }
}
int main(){
    freopen("input.txt", "r", stdin);
    int T;
    cin>>T;
    for(int tc=1; tc<=T; tc++){
        bestPrice=9999999;
        cin>>n;
        for(int i=1; i<=n; i++) cin>>Market[i];
        cin>>m;
        for(int i=1; i<=m; i++){
            cin>>ComboPrice[i]>>Combo[i][0];
            for(int j=1; j<=Combo[i][0]; j++) cin>>Combo[i][j];
        }
        cin>>l;
        for(int i=1; i<=l; i++) {
            cin>>needItem[i];
            Visit[needItem[i]]=0;
        }
        Try(1,0);
        cout<<"#"<<tc<<" "<<bestPrice<<endl;
    }
    return 0;
}

////Input
50
10
68 63 83 94 55 35 12 63 30 17 
4
104 3 2 6 3 
31 3 2 5 3 
81 4 3 2 7 9 
42 1 7 
6 9 10 3 8 6 5 
4
40 52 12 94 
2
58 2 1 4 
15 1 2 
3 4 2 3 
8
61 91 11 32 33 59 77 24 
5
81 2 2 3 
13 3 6 2 5 
78 2 5 3 
9 1 7 
9 1 5 
4 8 3 4 2 
11
61 9 82 30 86 58 34 31 19 30 93 
12
24 2 3 8 
151 3 11 4 9 
142 3 7 3 10 
18 2 7 6 
207 5 8 5 7 2 11 
65 2 11 8 
16 3 3 1 11 
36 1 2 
150 4 10 7 2 8 
3 1 8 
20 1 2 
138 5 11 5 8 6 7 
6 3 10 9 1 5 8 
3
11 72 66 
8
8 1 2 
3 1 1 
18 1 2 
32 1 3 
19 1 3 
28 1 2 
34 1 2 
15 1 2 
1 1 
6
32 4 11 99 24 55 
3
40 1 1 
111 3 6 3 2 
73 2 1 5 
4 3 6 5 4 
9
66 61 18 58 34 75 29 36 66 
6
62 2 1 4 
32 1 4 
22 3 5 3 1 
10 1 9 
25 1 9 
6 4 6 1 7 8 
6 2 9 8 7 5 3 
4
78 46 92 82 
14
68 2 3 2 
129 2 2 1 
28 1 4 
134 2 1 4 
56 2 2 3 
56 2 4 2 
66 1 2 
68 1 4 
37 1 2 
41 1 3 
36 2 4 2 
85 2 1 2 
19 2 2 3 
38 1 2 
2 1 3 
4
57 86 72 66 
0
3 1 4 2 
7
93 58 20 97 20 6 90 
5
122 3 1 4 7 
107 3 4 5 2 
18 1 6 
53 3 1 5 4 
18 1 1 
5 7 2 1 4 3 
5
36 52 59 44 35 
4
43 1 2 
79 2 1 4 
60 2 3 2 
5 1 3 
2 4 5 
3
45 11 21 
10
20 1 2 
1 1 3 
9 1 3 
5 1 2 
11 1 2 
3 1 1 
5 1 2 
8 1 2 
28 1 2 
23 1 3 
1 3 
10
88 37 61 62 59 64 23 76 21 52 
13
122 3 9 4 1 
59 3 4 7 8 
44 2 6 5 
47 1 7 
23 1 2 
40 2 8 4 
37 1 5 
164 4 1 2 3 10 
2 1 9 
158 4 8 1 9 10 
17 4 8 5 9 4 
38 3 1 9 4 
236 5 1 2 5 6 7 
7 1 4 6 7 8 2 10 
9
17 15 46 85 3 84 70 73 74 
2
48 2 5 4 
86 4 7 3 8 4 
4 2 6 3 7 
4
69 79 23 69 
10
9 2 3 4 
82 2 4 2 
21 2 3 2 
85 2 3 4 
56 2 3 2 
49 1 2 
2 1 3 
21 1 1 
16 2 4 3 
21 1 2 
2 3 1 
9
42 8 84 75 48 17 28 83 96 
13
66 4 9 7 2 3 
154 3 7 8 4 
88 3 2 4 9 
24 4 6 1 2 5 
86 4 7 8 4 9 
30 1 2 
6 4 3 2 4 6 
46 2 2 8 
73 2 4 2 
175 4 5 2 8 4 
11 3 6 7 9 
96 2 1 6 
20 3 4 7 6 
6 6 7 5 9 4 8 
8
55 7 38 12 61 22 86 2 
10
34 1 4 
25 2 3 7 
39 2 8 2 
17 2 2 5 
77 2 7 2 
13 4 1 8 3 4 
32 2 8 1 
24 2 6 5 
4 4 1 8 6 2 
122 4 2 5 7 1 
4 6 7 3 1 
3
73 47 79 
14
41 1 1 
18 1 1 
46 1 2 
11 1 2 
21 1 2 
31 1 1 
30 1 2 
7 1 3 
47 1 3 
10 1 3 
22 1 3 
25 1 2 
54 1 2 
23 1 1 
1 2 
6
98 85 36 26 55 40 
5
5 2 5 6 
16 1 3 
56 1 2 
33 1 5 
21 1 5 
3 4 3 1 
5
10 68 3 69 1 
3
30 1 3 
20 2 4 1 
4 1 4 
2 1 2 
14
43 81 53 97 77 1 95 91 84 43 57 93 70 65 
16
23 1 11 
11 3 2 8 10 
45 3 10 2 7 
179 4 3 12 13 4 
14 5 8 12 4 14 2 
1 3 14 1 12 
56 4 4 5 2 1 
6 1 9 
131 7 13 9 10 4 14 3 2 
213 5 3 11 4 13 6 
254 6 14 1 13 5 4 10 
92 2 8 6 
86 2 11 8 
48 3 7 9 6 
179 4 9 14 12 3 
74 3 8 6 7 
12 13 7 9 10 4 1 11 3 2 8 12 14 
14
55 92 13 59 30 53 19 23 50 99 58 80 26 94 
21
126 6 9 5 6 11 2 7 
43 1 4 
27 7 11 10 3 14 4 6 5 
141 4 1 6 7 11 
249 6 4 6 8 3 9 11 
61 6 13 10 9 8 12 6 
366 7 3 4 13 6 7 11 12 
267 7 6 7 14 5 4 12 9 
171 4 5 7 11 12 
56 1 12 
98 2 14 6 
75 5 13 10 1 14 11 
5 1 6 
51 5 4 1 12 8 5 
97 5 12 5 4 7 13 
8 4 14 12 10 9 
272 7 7 3 4 2 11 6 9 
77 5 13 5 6 11 4 
20 6 10 4 6 8 12 5 
48 7 6 5 11 10 3 14 12 
190 5 2 9 7 3 6 
11 9 7 3 2 13 5 11 10 12 4 1 
13
95 88 64 1 73 31 9 62 7 23 90 76 64 
17
115 3 1 8 9 
40 1 8 
165 5 3 4 10 5 1 
29 1 6 
188 5 11 7 9 3 4 
15 2 4 11 
165 6 10 4 9 3 8 2 
142 3 9 13 6 
47 4 13 10 12 9 
8 1 7 
51 6 12 11 10 4 8 6 
95 4 6 2 7 12 
25 1 6 
70 5 13 12 10 6 1 
18 2 6 4 
38 1 12 
54 6 5 1 13 4 3 10 
11 3 5 8 7 1 12 9 10 11 6 13 
13
21 1 28 39 18 17 49 1 51 80 4 86 46 
18
92 4 10 8 12 3 
2 2 5 8 
8 1 2 
34 5 11 9 6 12 7 
31 2 4 8 
163 5 10 12 8 6 7 
94 3 13 7 2 
24 6 12 7 10 8 1 9 
50 2 5 4 
27 1 6 
4 3 10 6 13 
126 6 10 8 1 5 6 4 
13 4 1 8 12 4 
65 2 8 10 
10 1 4 
19 3 6 9 5 
41 1 8 
11 5 5 7 6 9 4 
11 3 12 7 8 5 4 1 11 2 6 10 
16
26 40 28 91 6 33 14 14 53 78 58 44 73 5 59 79 
14
54 2 8 1 
79 5 3 12 10 15 8 
82 2 4 7 
154 5 4 9 14 6 13 
170 4 11 9 16 8 
283 6 13 4 11 1 15 10 
230 6 13 3 16 14 1 6 
24 4 6 10 1 5 
152 5 16 11 3 12 5 
90 2 10 2 
195 6 7 15 13 4 12 14 
24 3 2 15 6 
42 6 7 3 16 9 1 11 
131 3 10 16 12 
9 16 2 11 8 1 15 5 14 7 
17
49 14 10 49 96 65 30 71 58 76 81 41 30 41 81 71 47 
5
288 6 2 10 7 4 8 9 
32 3 4 11 12 
45 1 7 
61 4 3 9 8 12 
102 2 14 5 
13 10 7 14 4 9 6 12 16 3 5 13 17 11 
11
87 56 8 80 47 20 29 46 50 31 66 
5
7 1 9 
30 4 11 2 5 3 
36 1 11 
47 4 2 9 3 4 
36 5 11 5 2 9 1 
8 4 3 11 6 1 8 10 5 
15
25 77 72 41 86 41 28 82 6 11 47 16 10 51 48 
1
93 3 14 6 15 
7 2 14 10 8 7 4 13 
13
24 62 28 37 88 62 27 5 2 22 88 93 77 
17
9 4 13 10 1 12 
197 5 8 3 13 11 7 
92 4 7 1 4 13 
20 2 6 12 
113 4 7 9 6 3 
165 5 5 13 10 2 9 
61 2 8 4 
183 4 5 6 11 13 
4 5 6 13 9 1 2 
75 2 1 6 
81 6 8 7 2 9 1 4 
176 5 4 6 2 9 8 
75 3 4 6 10 
46 1 7 
88 2 13 8 
42 2 12 1 
34 2 13 5 
9 11 10 7 12 2 9 4 1 6 
11
27 17 58 87 28 97 29 30 57 96 39 
21
8 3 5 10 11 
34 5 7 4 2 10 5 
105 3 11 2 6 
126 4 2 7 6 3 
53 4 5 4 6 10 
83 3 10 5 3 
20 2 11 2 
76 2 10 1 
89 2 1 2 
19 1 6 
4 4 6 3 5 2 
145 4 5 1 11 9 
110 4 4 11 5 10 
180 4 3 4 5 10 
10 1 9 
264 5 8 9 2 5 4 
62 4 11 10 5 9 
9 1 3 
19 2 1 3 
98 3 10 7 1 
25 5 2 10 4 3 7 
7 11 8 2 1 9 4 5 
17
26 67 98 58 8 61 83 45 85 14 55 7 6 28 13 47 9 
20
334 8 11 13 6 10 3 1 16 8 
136 4 4 14 6 17 
127 3 9 2 5 
36 3 4 16 15 
70 4 17 4 1 16 
27 8 14 5 3 11 6 10 13 7 
43 2 12 17 
103 4 7 4 8 9 
108 6 7 8 15 3 9 5 
52 2 17 6 
97 4 6 7 1 9 
46 1 6 
144 3 3 17 1 
141 8 9 12 6 5 17 3 8 2 
99 8 8 9 3 16 14 4 10 2 
175 8 13 11 2 1 3 8 7 4 
288 7 2 7 14 3 15 16 6 
103 2 10 2 
159 5 14 10 6 12 7 
13 2 5 7 
13 5 14 16 11 13 2 3 4 1 8 9 10 15 
19
75 29 39 37 75 69 3 79 95 50 94 14 33 88 9 69 34 95 78 
28
370 9 5 9 13 1 15 10 17 3 11 
160 6 2 14 9 4 7 12 
47 1 8 
100 3 17 8 9 
338 7 12 17 11 2 10 5 3 
86 4 4 11 15 7 
41 1 10 
96 2 1 11 
185 5 17 18 1 7 2 
37 1 13 
254 8 10 14 19 1 7 12 6 13 
60 2 16 19 
27 1 5 
202 5 17 4 13 3 14 
117 6 18 11 16 17 19 7 
91 4 18 5 16 13 
164 6 7 2 10 14 13 19 
94 3 9 13 3 
39 2 6 13 
237 5 8 14 11 1 16 
173 4 6 14 4 5 
171 6 7 5 13 2 11 4 
76 2 19 5 
21 6 9 15 14 3 19 10 
25 2 19 9 
26 8 4 18 3 9 8 13 1 17 
211 7 13 17 9 2 14 10 15 
174 4 11 10 3 19 
13 2 8 10 15 9 3 1 12 5 18 6 7 13 
13
74 14 1 44 93 77 80 76 96 88 80 95 46 
15
6 4 6 4 12 7 
50 2 3 8 
5 1 6 
136 5 10 6 12 2 7 
103 6 13 2 9 1 7 8 
190 5 7 2 1 3 12 
167 4 2 7 11 1 
89 3 3 8 11 
55 4 1 7 2 10 
115 6 2 6 4 1 9 8 
42 5 3 13 2 6 9 
18 5 5 6 4 7 9 
147 6 9 2 5 3 10 6 
209 6 12 13 3 10 1 5 
112 6 12 11 10 13 8 2 
8 1 3 12 6 11 13 2 7 
16
57 37 39 8 25 26 63 85 24 12 40 34 2 28 68 15 
0
14 15 7 3 6 9 1 13 16 14 5 4 12 8 11 
18
9 17 68 80 94 86 9 87 28 96 35 87 61 99 95 54 52 45 
4
89 6 4 13 6 3 18 14 
103 2 4 9 
389 8 8 16 1 15 7 18 17 11 
279 7 4 11 6 1 2 13 5 
15 8 12 3 4 1 11 16 14 6 7 17 2 15 13 5 
12
50 31 70 44 94 35 68 57 2 46 99 75 
14
84 3 1 10 8 
187 6 8 10 7 2 9 1 
217 5 2 5 4 12 7 
177 4 3 1 10 8 
217 6 3 7 4 8 5 12 
131 6 10 4 9 7 6 3 
172 5 9 1 3 6 5 
1 4 9 5 4 1 
44 2 10 2 
73 4 11 1 6 4 
47 3 9 5 2 
24 3 9 7 3 
82 2 11 8 
42 3 5 4 6 
11 10 7 11 6 12 1 8 2 9 4 5 
12
79 39 87 87 20 54 44 88 70 58 14 66 
7
67 3 7 3 5 
48 2 9 1 
2 1 4 
12 2 6 4 
73 6 1 6 11 3 9 7 
18 1 3 
68 6 1 12 6 10 9 11 
9 10 3 6 1 7 11 4 2 9 
17
46 6 41 98 77 19 82 20 24 13 33 83 24 7 68 27 38 
3
88 2 10 7 
233 5 8 2 1 5 13 
77 3 5 6 10 
8 7 3 16 2 9 8 10 13 
14
42 27 19 12 59 88 93 39 35 78 39 81 26 81 
15
18 1 4 
3 3 9 7 1 
16 5 9 8 2 10 14 
120 3 2 14 9 
34 1 4 
38 7 13 14 5 4 3 10 2 
95 5 9 7 11 14 10 
17 1 11 
156 7 6 7 8 11 3 5 9 
34 1 6 
13 2 6 9 
51 4 11 7 6 10 
182 5 7 12 9 6 1 
49 2 1 4 
58 4 9 8 12 6 
7 2 11 3 7 14 10 8 
19
87 35 43 52 35 88 79 32 85 56 6 79 34 58 27 24 76 70 61 
18
110 6 16 6 17 9 7 4 
183 6 5 15 19 14 1 2 
25 1 3 
1 1 7 
367 8 19 14 8 16 18 7 17 1 
116 3 4 14 18 
165 5 19 18 17 1 13 
32 1 2 
8 1 7 
96 3 17 13 7 
52 3 17 10 18 
20 1 1 
23 3 3 16 1 
28 1 7 
135 6 15 4 18 7 14 9 
21 1 16 
45 1 7 
222 5 17 10 6 1 3 
12 15 13 16 9 17 6 4 18 10 1 14 19 
11
43 9 61 10 33 57 51 72 49 69 95 
29
200 4 8 3 5 9 
11 4 2 1 7 11 
36 2 7 2 
57 2 9 5 
78 2 9 2 
20 4 1 7 5 6 
107 3 11 9 3 
4 3 8 6 11 
1 2 6 10 
25 4 11 6 10 7 
99 5 1 7 3 10 5 
236 5 8 6 3 9 4 
76 2 3 2 
95 4 9 6 1 8 
74 4 11 7 3 8 
170 4 10 1 5 3 
79 3 9 1 7 
32 1 7 
91 3 11 3 8 
163 4 10 3 9 11 
99 5 4 2 9 7 8 
209 5 3 6 10 9 11 
182 4 2 11 1 3 
91 2 4 3 
28 1 5 
143 4 8 1 10 9 
22 1 11 
25 1 5 
14 2 4 11 
5 7 8 10 1 4 
16
31 65 17 70 28 16 67 27 86 97 6 63 72 71 46 26 
22
23 2 13 6 
3 2 15 14 
222 5 14 8 10 4 6 
16 1 13 
33 1 14 
165 7 12 9 1 11 7 13 6 
33 3 2 5 12 
106 4 1 14 9 15 
130 3 6 4 16 
78 2 15 13 
93 3 6 5 10 
3 2 5 2 
295 8 14 2 15 13 4 8 3 12 
9 3 9 11 2 
22 1 9 
227 7 8 6 12 7 1 14 4 
34 1 5 
132 3 8 2 10 
41 1 4 
95 2 15 1 
92 5 5 6 4 14 8 
7 1 9 
15 5 3 13 4 16 8 10 6 7 2 14 15 9 12 1 
15
96 5 67 21 87 5 37 17 93 42 50 53 58 47 81 
22
6 1 2 
100 5 1 9 11 13 5 
226 5 12 6 4 9 3 
96 2 8 2 
254 6 14 6 12 10 5 15 
210 6 13 15 11 2 7 4 
28 3 8 12 10 
31 3 1 5 11 
24 1 12 
37 1 3 
194 6 15 12 8 11 6 4 
207 7 10 9 7 1 12 11 6 
248 6 4 7 10 6 9 2 
51 4 15 9 2 1 
7 3 14 7 13 
258 7 14 10 15 11 7 6 13 
47 3 8 1 13 
47 3 3 8 5 
96 4 7 5 1 12 
77 2 8 10 
13 4 7 15 8 6 
63 5 5 2 11 6 14 
9 2 8 15 9 6 5 10 1 14 
12
5 1 51 19 97 13 74 51 57 29 92 47 
22
27 3 3 9 2 
27 1 4 
258 6 8 6 3 9 1 10 
32 6 8 4 9 3 1 5 
178 4 11 6 8 7 
30 2 11 2 
188 5 9 2 8 7 3 
160 4 12 9 7 10 
2 1 7 
33 1 5 
130 5 1 2 6 10 7 
43 2 5 7 
45 5 7 6 9 8 3 
86 2 2 4 
86 2 1 10 
33 1 9 
48 1 6 
23 3 12 7 5 
167 6 10 4 1 6 11 5 
69 6 2 11 6 3 9 8 
54 2 1 9 
124 3 5 7 3 
7 5 11 12 10 1 6 3 
13
56 43 99 36 77 59 50 53 21 34 67 16 84 
6
64 2 12 11 
76 4 1 10 13 4 
268 6 10 11 4 13 1 8 
242 6 7 11 6 1 5 13 
88 2 6 4 
268 6 2 3 6 4 13 10 
9 2 9 6 7 10 8 11 3 1 
16
19 31 19 46 23 88 60 20 13 80 19 85 71 12 71 87 
10
48 1 6 
253 6 8 3 11 12 14 9 
37 1 9 
16 1 2 
42 6 8 16 1 13 10 2 
309 8 8 12 11 10 13 15 5 1 
146 3 2 3 6 
39 1 4 
5 2 2 10 
42 4 8 6 2 1 
11 2 3 13 1 8 9 7 11 14 5 15 
12
95 67 33 90 5 94 72 3 63 60 79 18 
27
224 5 2 11 8 3 10 
64 5 8 5 6 1 10 
121 4 3 4 11 1 
134 5 2 11 1 7 3 
79 5 7 9 12 8 5 
34 1 12 
12 1 9 
111 5 8 3 12 7 4 
39 1 9 
44 4 9 8 1 11 
120 4 2 6 11 10 
36 6 4 9 7 2 10 1 
96 2 7 6 
131 4 10 4 6 12 
14 2 3 5 
28 3 5 6 9 
22 5 9 12 5 6 7 
137 5 11 12 9 2 7 
39 4 5 4 2 7 
50 3 4 5 3 
49 4 7 12 8 2 
83 2 8 4 
118 3 9 5 4 
143 5 12 11 3 1 2 
132 5 5 6 10 9 1 
120 5 11 1 3 7 10 
46 1 8 
7 10 3 4 2 12 9 6 
14
92 81 27 38 74 84 74 80 69 12 90 97 24 20 
11
139 4 5 13 1 10 
71 5 5 1 11 3 14 
72 3 4 8 12 
215 4 9 10 2 6 
45 1 2 
54 5 13 1 4 10 12 
101 4 2 14 9 10 
82 2 12 3 
262 7 8 2 14 1 4 11 9 
158 5 11 12 2 9 14 
52 4 8 12 14 7 
13 11 8 9 12 5 7 14 2 13 3 6 10 1 
13
35 33 87 28 86 34 80 40 14 17 37 31 21 
7
268 6 8 10 13 9 7 2 
92 2 10 2 
27 1 6 
19 2 10 13 
7 1 7 
135 3 7 11 6 
90 5 1 8 10 9 6 
9 12 6 2 10 7 5 11 8 13 
20
50 42 21 81 91 9 83 96 39 33 46 12 75 21 65 62 7 58 39 55 
13
310 7 3 17 5 10 13 7 16 
321 7 13 20 16 18 5 15 4 
125 5 3 2 14 18 1 
201 6 6 2 3 9 16 7 
27 1 9 
403 10 18 14 9 15 3 17 4 11 13 10 
196 4 20 3 10 15 
45 10 19 15 7 4 13 9 14 8 18 16 
152 10 5 20 2 8 17 13 6 9 12 16 
6 6 17 13 19 10 1 5 
47 1 7 
182 4 15 12 9 19 
255 5 18 14 3 5 4 
12 6 12 3 5 10 16 11 7 9 2 20 4