題目連結
題目大意
題目第一行input是w, 表示這個workyard有幾pile的物品，後面有w行，一行一個pile，表示每一樣物品的價格。物品的成本價是10元，每一疊的物品要從第一個開始拿，拿到有最大的profit。output要輸出這是第幾個workyard(testcase)，最大利益及要買幾樣物品(多解)。
解題思路
找出每一疊物品的最大利益，及可以買幾個（可能有多組解）。後用bfs彼此相加。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <cstdio>#include <stdlib.h>#include <string.h>using namespace std;int profits[21];int profit_pruls_index[51][22];int num_to_buy[1005];int num_index=0, w;void add_recursive(int piles_num, int index) { int i; if (piles_num>=w) { num_to_buy[index] = 1; return ; } for (i = 1; i <= profit_pruls_index[piles_num][0]; i++) add_recursive(piles_num+1, index+profit_pruls_index[piles_num][i]);}int main(){ int b, i, j, p,each_max_profit=0, tmp_profit, tmp_index, max_profit=0, workyards=0; while (scanf("%d",&w)==1 && w) { workyards++; max_profit = 0; num_index = 0; for (i = 0; i < w; i++) { scanf("%d",&b); tmp_profit = 0; each_max_profit = 0; for (j = 0; j < b; j++){ scanf("%d", &p); tmp_profit += 10-p; profits[j] = tmp_profit; if (tmp_profit>each_max_profit) each_max_profit = tmp_profit; } max_profit += each_max_profit; tmp_index = 1; for (j = 0; j < b; j++) { if (profits[j]==each_max_profit){ if (profits[j]==0){ profit_pruls_index[i][tmp_index] = 0; tmp_index++; } profit_pruls_index[i][tmp_index] = j+1; tmp_index++; } } if (tmp_index==1){ profit_pruls_index[i][0] = 1; profit_pruls_index[i][1] = 0; } else profit_pruls_index[i][0] = tmp_index-1; } if (workyards!=1) printf("\n"); printf("Workyards %d\n",workyards); printf("Maximum profit is %d.\n", max_profit); printf("Number of pruls to buy:"); for (j=0; j< 1005; j++) num_to_buy[j] = 0; add_recursive(0, 0); int print_count=0; for (j = 0; j < 1005; j++) { if (print_count==10) break; if (num_to_buy[j]) { printf(" %d", j); print_count++; } } printf("\n"); } return 0;} |
