NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 28 题

（连续邮资问题）某国发行了 $n$ 种不同面值的邮票，并规定每封信最多允许贴 $m$ 张邮票，在这些约束下，为了能贴出 $\{1,2,3,\dots,\mathrm{maxvalue}\}$连续整数集合的所有邮资，并使 $\mathrm{maxvalue}$ 的值最大，应该如何设计各邮票的面值？例如，当 $n=5,m=4$ 时，面值设计为 $\{1,3,11,15,32\}$，可使 $\mathrm{maxvalue}$ 达到最大值 $70$（或者说，用这些面值的 $1$ 至 $4$ 张邮票可以表示不超过 $70$ 的所有邮资，但无法表示邮资 $71$。而用其他面值的 $1$ 至 $4$ 张邮票如果可以表示不超过 $k$ 的所有邮资，必有 $k\leq70$）。

下面是用递归回溯求解连续邮资问题的程序。数组 x[1:n] 表示 $n$ 种不同的邮票面值，并约定各元素按下标是严格递增的。数组 bestx[1:n] 存放使 $\mathrm{maxvalue}$ 达到最大值的邮票面值（最优解），数组 y[maxl] 用于记录当前已选定的邮票面值 x[1:i] 能贴出的各种邮资所需的最少邮票张数。请将程序补充完整。

#include <stdio.h>
#define NN	20
#define maxint	30000
#define maxl	500 /*邮资的最大值*/
int n, m, bestx[NN], x[NN], y[maxl], maxvalue = 0;
void result()
{
	//输出结果： 最大值：maxvalue 及最优解：bestx[1:n]（略）
}


void backtrace( int i, int r )
{
	int j, k, z[maxl];
	for ( j = 0; j <= ①; j++ )
		if ( y[j] < m )
			for ( k = 1; k <= m - y[j]; k++ )
				if ( y[j] + k <= y[②] )
					y[③] = y[

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是回溯法搜面值组合，配合背包DP算当前面值能凑出的最大连续邮资。拿到题先想：y[j]存凑j所需最少张数，每次加一张新面值x[i]后，用DP更新y数组，同时推进r（最大连续值）。填空时注意：循环上界是上一个面值能凑到的最大连续值，新邮资是旧邮资加若干张新面值，且要剪枝只算不超过当前r的。

最容易错的是循环上界写成maxl或写成r，导致DP多算无用状态；更新y时把下标搞混，把j+x[i-1]*k错写成j+x[i]*k；还有把r-1写成r，导致记录的最大连续值多1。另外在递归里忘记先把y拷贝给z，直接改y会让后面分支污染数据。这些坑都会让maxvalue算错或程序逻辑跑偏。

考点与概念

本题考查回溯法与背包DP的结合。y[j]表示用已选邮票凑出邮资j所需的最少张数；r表示当前已选邮票能连续凑出的最大邮资（即y[0]~y[r]都小于m，y[r+1]>=m）。maxvalue记录全局最优的r-1。x数组存当前递归层尝试的面值，必须严格递增，所以x[i]至少是x[i-1]+1。

命题视角

命题人喜欢在这里挖两个坑：一是循环上界，二是更新y的下标。因为y只关心小于m张数能凑出的连续值，所以j循环到r就够了，再多算r+1及以后既浪费又不会改变r。二是新邮资的计算：在已有y[j]张数基础上，再加k张新面值x[i]，得到j+x[i-1]*k（注意这里用x[i-1]是因为x[i-1]是上一层已确定的面值，而当前层x[i]还没确定，DP更新用的是上一层的面值）。很多同学会误写成j+x[i]*k，结果完全不对。

思考心法

1. 先确定y数组的上界：既然y[0]~y[r]都小于m，y[r+1]>=m，那么新面值只能影响j<=r的状态，所以j循环到r即可。 2. 对于每个j<y[j]+k，新邮资是j+x[i-1]*k，更新y[j+x[i-1]*k] = min(y[j+x[i-1]*k], y[j]+k)。 3. 更新完y后，重新找r：从r开始往后扫，直到遇到y[r]>=maxint（表示r+1已无法用< m张凑出），此时r就是新的最大连续值。 4. 当i>n时，如果r-1 > maxvalue，更新maxvalue和bestx。 5. 回溯时，先把y拷贝给z，再尝试下一个面值x[i]，然后递归调用backtrace(i+1, r)，回到上一层再把y恢复成z。

逐空推演

① y[j] < m 的循环上界。因为y[0]~y[r]都小于m，y[r+1]>=m，所以j只要扫到r就够了，再多扫只会算无用状态。填r。

② 更新y的下标。已有y[j]张数，再加k张新面值x[i]，新邮资是j + x[i-1]*k。填j + x[i-1]*k。

③ 同样填j + x[i-1]*k，表示把y[j]+k写到这个新邮资位置。

④ 更新maxvalue。r是当前最大连续值，而题目定义maxvalue是最大连续整数集合的上限，即r-1。填r - 1。

⑤ 面值x[i]的下界。x必须严格递增，所以x[i]至少是x[i-1]+1。填x[i-1] + 1。

⑥ 递归调用。在尝试完x[i]后，要进入下一层i+1，同时r可能已经变大，所以传r进去。填backtrace(i+1, r)。

避坑指南

• 循环上界别写成maxl，那样DP复杂度爆炸。
• 更新y时下标别用x[i]，要用x[i-1]，因为当前层x[i]还没确定。
• 更新完y后一定要重新找r，不能沿用上一层的r，否则可能漏掉新的连续值。
• 回溯时别忘记把y拷贝给z，否则不同分支会互相污染。
• maxvalue别记成r，题目明确是r-1。

考频与趋势

回溯法在题库共考过9题，覆盖6个考试级别，逐年分布：2007年1题、2009年1题、2010年1题、2012年1题、2020年1题、2025年4题；分赛事：NOIP提高组初赛3题、GESP五级2题、CSP提高级1题、GESP八级1题、CSP入门级1题、NOIP普及组初赛1题。本题就是2007年NOIP提高组初赛第28题，属于经典回溯+DP综合题。

记忆化搜索也考了5题，逐年：2007年1题、2025年2题、2026年2题，分赛事：CSP提高级1题、GESP五级1题、GESP八级1题、GESP六级1题、NOIP提高组初赛1题。

预测

从数据看，2025年回溯法考了4题，2026年记忆化搜索考了2题，说明近年对搜索类题目有持续偏好。未来可能继续考回溯+DP或记忆化搜索的综合题，难度略有提升，比如增加剪枝条件或要求输出多组解。暂无足够依据预测具体年份和题型变化，但建议重点复习回溯框架和DP状态更新细节，这类题目每年都有变种出现。