Posted on 2008-03-22 15:53
superman 閱讀(458)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1013 C++ 00:03.25 2804K */
2 #include <stdio.h>
3 #include <string.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int n;
9 int w1, s1, d1;
10 int w2, s2, d2;
11 int w3, s3, d3;
12 int c1, c2, c3, d4;
13 int opt[2][501][501];
14 struct { int w, s; } caravan[101];
15
16 int put(int k, int i, int j)
17 {
18 int w = (caravan[k].w - i * w1 - j * w2) / w3;
19 int s = (caravan[k].s - i * s1 - j * s2) / s3;
20 if(w <= 0 || s <= 0) return 0;
21 return (w < s ? w : s);
22 }
23
24 int main()
25 {
26 int cs = 0;
27 while(cin >> n)
28 {
29 if(n == 0)
30 break;
31 cin >> w1 >> s1 >> d1;
32 cin >> w2 >> s2 >> d2;
33 cin >> w3 >> s3 >> d3;
34 cin >> c1 >> c2 >> c3 >> d4;
35 for(int i = 1; i <= n; i++)
36 cin >> caravan[i].w >> caravan[i].s;
37
38 memset(opt, 0, sizeof(opt));
39
40 opt[0][0][0] = 0;
41 int mx = 0, my = 0;
42 for(int k = 1; k <= n; k++)
43 {
44 memset(opt[1], 0XFF, sizeof(opt[1]));
45 int mmx = mx, mmy = my;
46 for(int i = 0; i <= mx; i++)
47 for(int j = 0; j <= my; j++)
48 {
49 if(opt[0][i][j] == -1)
50 continue;
51 for(int p = 0; p * w1 <= caravan[k].w && p * s1 <= caravan[k].s; p++)
52 for(int q = 0; p * w1 + q * w2 <= caravan[k].w && p * s1 + q * s2 <= caravan[k].s; q++)
53 {
54 opt[1][i + p][j + q] >?= (opt[0][i][j] + put(k, p, q));
55 mmx >?= i + p;
56 mmy >?= j + q;
57 }
58 }
59 mx = mmx;
60 my = mmy;
61 memcpy(opt[0], opt[1], sizeof(opt[1]));
62 }
63 int max = 0;
64 for(int i = 0; i <= mx; i++)
65 for(int j = 0; j <= my; j++)
66 if(opt[0][i][j] >= 0)
67 {
68 if(d4 > c1 * d1 + c2 * d2 + c3 * d3)
69 {
70 int t1 = i, t2 = j, t3 = opt[0][i][j], cur = 0;
71 while(t1 - c1 >= 0 && t2 - c2 >= 0 && t3 - c3 >= 0)
72 {
73 t1 -= c1;
74 t2 -= c2;
75 t3 -= c3;
76 cur += d4;
77 }
78 cur += (t1 * d1 + t2 * d2 + t3 * d3);
79 max >?= cur;
80 }
81 else
82 max >?= (i * d1 + j * d2 + opt[0][i][j] * d3);
83 }
84 if(cs++)
85 cout << endl;
86 cout << "Case " << cs << ':' << ' ' << max << endl;
87 }
88 return 0;
89 }
90