「codevs1047」DP + 搜索

发表于 | 分类于

题目链接

给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。

例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。

输入描述 Input Description

N和K

输出描述 Output Description

每种邮票的面值，连续最大能到的面值数。数据保证答案唯一。

样例输入 Sample Input

3 2

样例输出 Sample Output

1 3
MAX=7

看过题面， 我们发现这好像可以通过搜索来AC， 但又要用到一定的动归思想，Go for it!

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
#include <cstdio>
#include <climits>
#include <iostream>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;
const int INF = 1e8;
int n, k, ans, sum; 
int a[1000 + 5], dp[1000 + 5]， b[1000 + 5];
//b数组用来储存结果， 因为a数组经过了多次变动；
//a数组用来储存起始数据；
//dp[i]达到i值最少需要多少张牌
inline int read() {
	char ch = getchar(); int flag = 1; int res = 0;
	while(ch > '9' || ch < '0') {if(ch == '-') flag = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {res = res * 10 + ch - '0'; ch = getchar();}
	return (res * flag);
}
void DP() {
	dp[1] = 1; int i; //赋初值
	for (i = 2; ; i++) {
		dp[i] = INF;
		for (int j = 1; j <= k && i - a[j] >= 0; j++) {
			dp[i] = min(dp[i], dp[i - a[j]] + 1);
		}
        //j <= k (j 是种类， 所以一定是<=K)
        //i - a[j] >= 0; 我们可以不选（dp[0] = 0）,但所选择的数值肯定是不能大于i的；
		if (dp[i] > n) break;
        //用的数量已经大于最大可选数量；
	}
	if (i - 1 > ans) {//因为i++，所以其实大1，故要减一，让新结果与旧的结果相比较；
		ans = i - 1;
		for (int i = 1; i <= k; i++)
		    b[i] = a[i];   
	}
}
void dfs(int x) { // 以第几种面值为参数
	if(x == k + 1) {
		DP(); return;
	}
	for(int i = a[x - 1] + 1; i <= a[x - 1] * n + 1; i++) {
		a[x] = i;
		dfs(x + 1); //一颗树形结构，不断向下分支，再return上去；
	}
    //a[x - 1] + 1 加上新数值最起码大1；
    //a[x - 1] * n + 1 加1保证其连续性， 加2的话就不再连续了；
}
int main() {
	n = read(); k = read();
	a[1] = 1; ans = k;
	dfs(2);
	for(int i = 1; i <= k; i++) cout << b[i] << " ";
	cout << endl;
	cout << "MAX=" << ans << endl;
    return 0;
}