NOIP中常见的典型例题.pdf

NOIP中常见的典型例题 陈启峰整理 叠 放 箱 子 • 【问题】 • 某港口有一批箱子，将其编号，分别为1至N。每一个箱 子的尺寸规格是一样的，现在要将其中某些箱子叠放起来， 箱子叠放的规则如下： • 一、每个箱子上最多只能直接叠放一个箱子； • 二、编号较小的箱子不能放在编号较大的箱子之上； • 三、每个箱子都给出了自身重量与可承受重量，每个箱子 之上的所有箱子重量之和不得超过该箱的可承受重量。 • 为了节约堆放场地，希望你编程从中选出最多个箱子， 使之能够在满足条件的情况下叠放起来。 • 【输入】 • 第一行是一个整数N （1≤N≤1000）。 • 以下共有N行，每行两个整数，中间以空 格分隔，分别表示每个箱子的自身重量与 可承受重量，两个数值均为小于等于3000 的正整数。 • 【输出】 • 第一行应当输出最多可叠放的箱子总数M。 【样例】 有五个箱子，如下表： 编号 自身重量 可承受重量 则最多 1 19 15 可以叠 放4个 2 7 13 箱子， 3 5 7 方案之 一如： 4 6 8 1、2、 5 1 2 3、5 分析 • 设F[i,j]表示第i个箱子到第N个箱子中总重量为j 的 最大箱子数。 • 考虑第i个箱子放与不放的情况。 F [i 1,j ] not select  F [i,j ] max  F [i 1,j weight [i]] 1 select  • 注意，能选的条件是 • j ≥ weight*i+ 并且capacity≥j-weight[i] 代码 • program CQF_BOX; • uses math; • const maxn=1000; • var weight,capacity:array[1..maxn] of longint; • f:array[1..maxn+1,0..6000] of longint; • n:longint; • procedure init; • var i:longint; • begin • readln(n); • for i:=1 to n do • readln(weight[i],capacity[i]); • end; • procedure work; • var i,j,ans:longint; • begin • fill