题意:
现有k种邮票面额, 一封信上最多贴h张邮票。
求能贴出的最大连续区间,即[1, max_value]这个区间内的所有面额都能贴出来。
并输出k种面额, h + k <= 9.
思路:
这是一个经典的数学问题:连续邮资问题。
1)面额为1的邮票肯定要选进去(不然连1都贴不出来, 还怎么连续)。
此时最大连续区间为 [1, h]
2)当 [1,i - 1], 前i - 1种邮票面额确定后, 第i种邮票面额的取值区间为:[x[i - 1] + 1, max_value + 1], x[]数组存放邮票面额。
枚举第i种邮票面额, 并更新[1, max_value]。
代码:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1024
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int h, k;
36 int n, ans;
37 int x[MAXM], y[MAXN];
38 int f[MAXM];
39 void init()
40 {
41 memset(x, 0, sizeof(x));
42 memset(y, 0x3f, sizeof(y));
43 memset(f, 0, sizeof(f));
44
45 x[0] = 1;
46 n = h;
47 ans = 0;
48 for(int i = 0; i <= n; i ++)
49 y[i] = i;
50 }
51 void dfs(int pos)
52 {
53 if(pos >= k)
54 {
55 if(n > ans)
56 {
57 ans = n;
58 for(int i = 0; i < k; i ++)
59 f[i] = x[i];
60 }
61 return ;
62 }
63
64 int temp[MAXN];
65 int temp_ans = n;
66 for(int i = 0; i < MAXN; i ++) temp[i] = y[i];
67
68 for(int val = x[pos - 1] + 1; val <= n + 1; val ++)
69 {
70 x[pos] = val;
71 for(int ww = 0; ww < x[pos - 1] * h; ww ++)
72 {
73 if(y[ww] >= h) continue;
74 for(int num = 1; num <= h - y[ww]; num ++)
75 if(y[ww] + num < y[ww + num * val] && (ww + num * val < MAXN))
76 y[ww + num * val] = y[ww] + num;
77 }
78
79 while(y[n + 1] < INF) n ++;
80
81 dfs(pos + 1);
82
83 n = temp_ans;
84 for(int i = 0; i < MAXN; i ++) y[i] = temp[i];
85 }
86 }
87
88 void solve()
89 {
90 init();
91 dfs(1);
92 for(int i = 0; i < k; i ++)
93 printf("%3d", f[i]);
94 printf(" ->%3d\n", ans);
95 }
96
97 int main()
98 {
99 while(scanf("%d %d", &h, &k) && (h + k))
100 {
101 solve();
102 }
103 return 0;
104 }