TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1061
  • 問題
  • P1061叠放箱子
    制限 : 時間制限 : 1000 MS   メモリ制限 : 65536 KB
    問題説明

    某港口有一批箱子,将其编号,分别为1至N。每一个箱子的尺寸规格是一样的,现在要将其中某些箱子叠放起来,箱子叠放的规则如下:
    一、每个箱子上最多只能直接叠放一个箱子;
    二、编号较小的箱子不能放在编号较大的箱子之上;
    三、每个箱子都给出了自身重量与可承受重量,每个箱子之上的所有箱子重量之和不得超过该箱的可承受重量。
    现有一空地刚好能放下一个箱子,希望你编程从中选出最多个箱子,使之能够在满足条件的情况下叠放起来。

    例如:有五个箱子,如下表:
    编号---自身重量---可承受重量
    1-----------19------------15
    2-----------7-------------13
    3-----------5-------------7
    4-----------6-------------8
    5-----------1-------------2

    则最多可以叠放4个箱子,方案之一如:1、2、3、5

    入力形式

    第一行是一个整数N(1≤N≤1000)。
    以下共有N行,每行两个整数,中间以空格分隔,分别表示每个箱子的自身重量与可承受重量,两个数值均为小于等于4000的正整数。

    出力形式

    只有一行,一个整数表示最多可叠放的箱子总数。

    サンプル入力

    5
    19  15
    7   13
    5   7
    6   8
    1   2

    サンプル出力

    4

    ヒント

    叠放的箱子是:
    5
    3
    2
    1