蓝桥杯算法提高VIP-邮票面值设计

题目

题目链接

题解

DFS+动态规划。

整体思路： 第i个邮票的面值的范围为：value[i] = value[i-1]+1 ~ mx[i-1]+1，其中value[i]表示第i个邮票的面值，mx[i]表示前i个邮票能构成的连续最大数；解释一下这个范围，第i个邮票的面值至少比第i-1个邮票的面值多1，且必须要不超过前i-1个邮票（默认都是最多n张）所能构成的最大面值+1，要是大于最大面值+1就无法满足连续了。 因此，如果我们知道前一个邮票的面值，那么我们就可以推出当前邮票的面值范围，枚举范围内的面值，进行深搜，当找完k个面值的邮票时，更新一下最大连续数即可。显然，我们现在知道第一个邮票的面值必然是1，因此，上述的深搜方式确实可以进行。

还有一个问题，如何确定mx[i]呢？ 我们不去直接考虑从前i种邮票中选取n张能构成的最大面值，而是考虑前i种邮票构成面值为j的最少张数。 即使得到最小张数了，我们如何确定mx[i]？对于前i种邮票，我们只需要从小到大遍历面值j，判断枚举到的j对应的最少张数是否大于n（n如题），只要遇到了大于n的面值j，就说明无法用n张构成面值j，不满足连续的要求，所以最多也就能构成面值为j-1了，我们就得到了前i-1种邮票选取最多n张所能构成的最大面值，即j-1。 理解了为什么，接下来讲讲怎么做。 当我们要计算mx[i]时，其实value[1~i]都已经在深搜的过程中枚举好了，那我们将求mx[i]的问题再进行简化。 求已知的若干个数，第i个数的值为a[i]，求构成数值为m的数，最少需要多少个数？ 比较经典的dp吧 ， 转移方程为dp[j] = min(dp[j], dp[j-a[i]]+1)（这是一维的，降维后是这个转移方程） 求mx也是一样的，我们先通过动态规划求出前i种邮票能构成面值为j的最少数量，之后从小到大枚举面值，遇到所需数量大于n的面值就break，跳出时的面值-1即为mx。

如果看了上面还是没思路，但是还想自己写代码的同学，可以看看下面提示的伪代码。

本题的伪代码：

代码

#include
using namespace std;
const int N = 13*13;

int n, k, ans, res[N], value[N], f[N];

int dp(int x) {
	memset(f, 0x3f, sizeof f); // 动规初始化 
	f[0] = 0;
	
	for(int i = 1;i  ans) {
			ans = mx;
			for(int i = 1;i n>>k;
	
	dfs(1, 0); // 第一个参数是现在要确定第几个邮票的面值，第二个参数是前面的邮票构成的最大连续数是多少 

	for(int i = 1;i