搜索/动规邮票面值设计

1 #include
2 #include
3
4 typedef long long LL;
5
6 const long long INF &＃61; 9999999999999LL;
7
8 LL N, K, ans;
9 LL f[43*43], res[43], ans_arr[43];
10
11 inline void _cpy(LL *t1, LL *t2)
12 {
13 for (LL i &＃61; 1; i <&＃61; K; &＃43;&＃43;i) t1[i] &＃61; t2[i];
14 return;
15 }
16
17 LL get_mx(LL t)
18 {
19 LL limit &＃61; res[t] * N, i, j;
20 for (i &＃61; 1; i <&＃61; limit; &＃43;&＃43;i) f[i] &＃61; INF;
21 f[0] &＃61; 0;
22 for (i &＃61; 1; i <&＃61; limit; &＃43;&＃43;i) {
23 for (j &＃61; 1; j <&＃61; t && i - res[j] >&＃61; 0; &＃43;&＃43;j)
24 f[i] &＃61; std::min(f[i], f[i - res[j]] &＃43; 1);
25 if (f[i] > N) return i-1;
26 }
27 return limit;
28 }
29
30 void dfs_K(LL step)
31 {
32 LL tmp &＃61; get_mx(step - 1);
33 if (step &＃61;&＃61; K &＃43; 1) {
34 if (ans tmp, _cpy(ans_arr, res);
35 return;
36 }
37 for (LL i &＃61; res[step - 1] &＃43; 1; i <&＃61; tmp &＃43; 1; &＃43;&＃43;i)
38 res[step] &＃61; i, dfs_K(step &＃43; 1);
39 return;
40 }
41
42 int main()
43 {
44 scanf("%lld%lld", &N, &K);
45 res[1] &＃61; 1;
46 dfs_K(2);
47 for (LL i &＃61; 1; i "%lld ", ans_arr[i]);
48 printf("%lld\nMAX&＃61;%lld\n", ans_arr[K], ans);
49 return 0;
50 }