Dotcpp > 试卷列表 > （连续邮资问题）某国发行了 n 种不同面值的邮票，并规

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规

"NOIP真题" 试卷中 NOIP第十三届全国青少年信息学奥林匹克联赛初赛试题[2007提高组] 中有题目如下：

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

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

#include<stdio.h>
#defineNN20
#definemaxint30000
#definemaxl500/* 邮资的最大值 */
int n,m,bestx[NN],x[NN],y[maxl],maxvalue=0;
void result()
{ 
	输出结果：最大值： maxvalue 及 最优解： bestx[1:n] （略）
}
void backtrace(inti,intr)
{
	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[j]+k;
	while(y[r]<maxint)r++;
	if(i>n)
	{
		if(r-1>maxvalue)
		{
			maxvalue= ④ ; 
			for(j=1;j<=n;j++)
			bestx[j]=x[j];
		}
		return;
	}
	for(k=0;k<maxl;k++)
	z[k]=y[k];
	for(j= ⑤ ;j<=r;j++)
	{
		x[i]=j;
		⑥ ;
		for(k=0;k<maxl;k++)
		y[k]=z[k];
	}
}
void main()
{
	int j;
	printf("inputn,m:\n");
	scanf( "%d%d",&n,&m);
	for(j=1;j<maxl;j++)
	y[j]=maxint;
	y[0]=0;x[0]=0;x[1]=1;
	backtrace(2,1);
	result();
}

共 18 分　

所属试卷：NOIP第十三届全国青少年信息学奥林匹克联赛初赛试题[2007提高组]

其它题目

如果一个模板声明列出了多个参数，则每个参数之间必须用逗

在下列原型所示的C++函数中，按“传值”方式传递参数的

下列关于函数的描述中，错误的是。

以下不属于 Python 语言保留字的是（）。

下面不属于对象基本特点的是（）。

假定已建立以下数据链表结构，且指针p和q已指向如下图所

有以下程序：程序的运行结果是。

请在下面程序的横线处填上适当内容，以使程序完整,并使运

关于多继承二义性的描述中，_____是错误的。

在函数内部可以通过关键字____________未定义

以下程序输出结果是_________。

以下程序时应用递归算法求某数a的平方根，请填空，求平方

在/home目录下查找文件名为。Profile的文件，

下面给出了一个SHELL程序，试对其行后有#（n）形式

在System V进程通讯方式中，ipc_perm结构

在一条命令中如何查找一个二进制命令 Xconfigur

从事物的特性到计算机中的数据表示，经历的三个领域是现实

在MySQL中，类型DECIMAL(8，2)中的2表示

某系统中有A、B两类资源各6个，/时刻资源分配及需求情

（8 分）假设计算机 M 的主存地址为 24 位，按字

(9分)43题的C语言代码，对应的机器级代码如下,请回

（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜

假设所有变量都为整型，表达式(a=2,b=5,a>b?

执行语句a=b=c;后a的值是_____。

则x的值为_____。

对于字符数为n个的字符串，其占用的内存为n+1个字节空

以下语句定义正确的是。

下列选项中不属于视频文件格式的是（）。

输入：11 3输出：（）

（棋盘覆盖问题）在一个 k k 2 × 2 个方格组成

更多选择题

更多填空题

题量:	0 道
总分:	分

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷