Posted on 2008-03-16 15:23
superman 閱讀(946)
評論(3) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1558 C++ 00:00.01 904K */
2 #include <limits.h>
3 #include <string.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int N, x[10], opt[2008];
9
10 int search(int n)
11 {
12 if(n == 0) return 0;
13 if(opt[n]) return opt[n];
14
15 opt[n] = INT_MAX;
16 for(int i = 1; i <= 6; i++)
17 if(n - x[i] >= 0)
18 opt[n] <?= search(n - x[i]) + 1;
19 for(int i = 1; i <= 6; i++)
20 if(n + x[i] <= 2000)
21 opt[n] <?= search(n + x[i]) + 1;
22 return opt[n];
23 }
24
25 int main()
26 {
27 cout.setf(ios_base::showpoint);
28 cout.setf(ios_base::fixed);
29 cout.precision(2);
30
31 cin >> N;
32 while(N--)
33 {
34 memset(x, 0, sizeof(x));
35 memset(opt, 0, sizeof(opt));
36
37 for(int i = 1; i <= 6; i++)
38 cin >> x[i];
39
40 int sum = 0, max = 0;
41 for(int i = 1; i <= 100; i++)
42 {
43 sum += search(i);
44 max >?= search(i);
45 }
46
47 cout << double(sum) / 100 << ' ' << max << endl;
48 }
49
50 return 0;
51 }
52