P2123 皇后游戏

    • 226通过
    • 572提交
  • 题目提供者 lin_toto 站长团
  • 评测方式 云端评测
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    还记得 NOIP 2012 提高组 Day1 的国王游戏吗?时光飞逝,光阴荏苒,两年

    过去了。国王游戏早已过时,如今已被皇后游戏取代,请你来解决类似于国王游

    戏的另一个问题。

    题目描述

    皇后有 n 位大臣,每位大臣的左右手上面分别写上了一个正整数。恰逢国庆

    节来临,皇后决定为 n 位大臣颁发奖金,其中第 i 位大臣所获得的奖金数目为第

    i-1 位大臣所获得奖金数目与前 i 位大臣左手上的数的和的较大值再加上第 i 位

    大臣右手上的数。

    形式化地讲:我们设第 i 位大臣左手上的正整数为 ai,右手上的正整数为 bi,

    则第 i 位大臣获得的奖金数目为 ci可以表达为:

    当然,吝啬的皇后并不希望太多的奖金被发给大臣,所以她想请你来重新安

    排一下队伍的顺序,使得获得奖金最多的大臣,所获奖金数目尽可能的少。

    注意:重新安排队伍并不意味着一定要打乱顺序,我们允许不改变任何一

    位大臣的位置。

    输入输出格式

    输入格式:

    第一行包含一个正整数 T,表示测试数据的组数。

    接下来 T 个部分,每个部分的第一行包含一个正整数 n,表示大臣的数目。

    每个部分接下来 n 行中,每行两个正整数,分别为 ai和 bi,含义如上文所述。

    输出格式:

    共 T 行,每行包含一个整数,表示获得奖金最多的大臣所获得的奖金数目。

    输入输出样例

    输入样例#1: 复制
    1
    3
    4 1
    2 2
    1 2
    输出样例#1: 复制
    8
    输入样例#2: 复制
    2
    5
    85 100
    95 99
    76 87
    60 97
    79 85
    12
    9 68
    18 45
    52 61
    39 83
    63 67
    45 99
    52 54
    82 100
    23 54
    99 94
    63 100
    52 68
    输出样例#2: 复制
    528
    902

    说明

    按照 1、2、3 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 10;

    按照 1、3、2 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 9;

    按照 2、1、3 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 9;

    按照 2、3、1 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 8;

    按照 3、1、2 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 9;

    按照 3、2、1 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 8。

    当按照 3、2、1 这样排列队伍时,三位大臣左右手的数分别为:

    (1, 2)、(2, 2)、(4, 1)

    第 1 位大臣获得的奖金为 1 + 2 = 3;

    第 2 位大臣获得的奖金为 max{3, 3} + 2 = 5;

    第 3 为大臣获得的奖金为 max{5, 7} + 1 = 8。

    对于全部测试数据满足: $T \le 10$ , $1 \le n \le 20\ 000$ , $1 \le a_i, b_i \le 10^9$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。