【问题描述】
【描述 Description 】
给定一个信封，最多只允许粘贴N张邮票，计算在给定M（N+M<=10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。 例如，N=3，M＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，M＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。 【样例输入】 共一行，两个整数，分表为N与M的值。 【输入格式 Input Format 】 一行，分别为N,M。 【输出格式 Output Format 】 两行。 第一行为m种邮票的面值，按升序排列，各数之间用一个空格隔开。 第二行为最大值。 【样例输入 Sample Input 】 3 2 【样例输出 Sample Output 】 1 3 MAX=7 算法分析 深搜加DP 栈记录所用邮票的面值 每次面值的搜索的范围为：上一次使用的邮票面值+1 to 上一次连续达到的最大值+1 然后DP，记录达到每个面值用的最少邮票数，不断更新最优解 注意要从第1张邮票开始，否则要出错 【代码】
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 | #include <stdio.h> int a[11], ans[11]; int b[1001]; int n, m, max; int dp(int i) { int j, k; for (j = 1; j < 1001; j++) b[j] = 9999; for (j = 1; j <= i; j++) b[a[j]] = 1; j = 0; do { j++; for (k = 1; k <= i; k++) if (j > a[k] && b[j - a[k]] + 1 < b[j]) b[j] = b[j - a[k]] + 1; }while (b[j] <= m); return j; } void search(int i) { int j, k; if (i > n) { if (dp(i - 1) - 1 > max) { for (j = 1; j <= 10; j++) ans[j] = a[j]; max = dp(i - 1) - 1; } return; } j = dp(i - 1); for (k = j ; k >= a[i - 1] + 1; k--) { a[i] = k; search(i + 1); } } int main() { int i; scanf("%d%d", &m, &n); max = 0; a[1] = 1; search(2); for (i = 1; i <= n; i++) printf("%d ", ans[i]); printf("\n"); printf("MAX=%d\n", max); return 0; } |