蓝桥杯算法提高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<bits/stdc++.h>
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 <= x;i ++)
	for(int j = value[i];j <= n*value[x];j ++) // j最大为 n*value[x]，即n张全选第x种邮票 
	f[j] = min(f[j], f[j-value[i]]+1);
	
	int i;
	for(i = 1;i <= n*value[x];i ++) if(f[i] > n) break;
	return i-1;
}

void dfs(int x, int mx) {
	if(x > k) {
		if(mx > ans) {
			ans = mx;
			for(int i = 1;i <= k;i ++) res[i] = value[i];
		}
		return ;
	}
	for(int i = value[x-1]+1;i <= mx+1;i ++) { // 枚举第x个邮票的面值范围 
		value[x] = i; 
		dfs(x+1, dp(x));
	}
}


int main()
{
	cin>>n>>k;
	
	dfs(1, 0); // 第一个参数是现在要确定第几个邮票的面值，第二个参数是前面的邮票构成的最大连续数是多少 

	for(int i = 1;i <= k;i ++) cout << res[i] << ' ';
	cout << endl << "MAX=" << ans;
	return 0;
}