洛谷P2123 皇后游戏

Bertha 。 2022-05-26 11:29 219阅读 0赞

## 题目背景 ##

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

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

戏的另一个问题。

## 题目描述 ##

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

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

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

大臣右手上的数。

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

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

![1257.png][]

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

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

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

位大臣的位置。

## 输入输出格式 ##

输入格式：

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

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

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

输出格式：

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

## 输入输出样例 ##

输入样例\#1： 复制

1
    3
    4 1
    2 2
    1 2

输出样例\#1： 复制

输入样例\#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*T*≤10,1 \\le n \\le 20\\ 0001≤*n*≤20000,1 \\le a\_i, b\_i \\le 10^91≤*a**i*,*b**i*≤109。

参考：[https://cnyali-lk.com/queen/][https_cnyali-lk.com_queen]

对于max和min的变换有了新认识

显然因为ai,bi>0a\_i,b\_i>0*a**i*,*b**i*>0 ，所以最后一个人拿到的钱一定最多。

所以只需要考虑最后一个人拿到的钱数即可。

考虑两个人的情况，第一个人左手上为a1a\_1*a*1，右手上为b1b\_1*b*1，第二个人左手上为a2a\_2*a*2，右手上为b2b\_2*b*2。

如果第一个人在前面，则第二个人拿到的钱数为max(a1\+b1,a1\+a2)\+b2=a1\+b2\+max(b1,a2)=a1\+b1\+a2\+b2−min(b1,a2)\\max(a\_1+b\_1,a\_1+a\_2)+b\_2=a\_1+b\_2+\\max(b\_1,a\_2)=a\_1+b\_1+a\_2+b\_2-\\min(b\_1,a\_2)max(*a*1\+*b*1,*a*1\+*a*2)\+*b*2=*a*1\+*b*2\+max(*b*1,*a*2)=*a*1\+*b*1\+*a*2\+*b*2−min(*b*1,*a*2)。

反之第一个人拿到的钱数则为max(a2\+b2,a2\+a1)\+b1=a2\+b1\+max(b2,a1)=a1\+b1\+a2\+b2−min(b2,a1)\\max(a\_2+b\_2,a\_2+a\_1)+b\_1=a\_2+b\_1+\\max(b\_2,a\_1)=a\_1+b\_1+a\_2+b\_2-\\min(b\_2,a\_1)max(*a*2\+*b*2,*a*2\+*a*1)\+*b*1=*a*2\+*b*1\+max(*b*2,*a*1)=*a*1\+*b*1\+*a*2\+*b*2−min(*b*2,*a*1)

如果第一个人在前面，则a1\+b1\+a2\+b2−min(b1,a2)<a1\+b1\+a2\+b2−min(b2,a1)a\_1+b\_1+a\_2+b\_2-\\min(b\_1,a\_2)<a\_1+b\_1+a\_2+b\_2-\\min(b\_2,a\_1)*a*1\+*b*1\+*a*2\+*b*2−min(*b*1,*a*2)<*a*1\+*b*1\+*a*2\+*b*2−min(*b*2,*a*1)

可以变为min(b2,a1)<min(b1,a2)\\min(b\_2,a\_1)<\\min(b\_1,a\_2)min(*b*2,*a*1)<min(*b*1,*a*2

)

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    typedef long long ll;
    #define Maxn 20009
    struct node
    {
    	ll l, r;
    }a[Maxn];
    int T; int n;
    ll dp[Maxn];
    int cmp(node a, node b)
    {
    	return min(a.l, b.r) < min(b.l, a.r);
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> T;
    	while (T--)
    	{
    		//memset(a, 0, sizeof(a));
    		cin >> n;
    		for (int i = 1; i <= n; i++)
    			cin >> a[i].l >> a[i].r;
    		sort(a + 1, a + 1 + n, cmp);
    		ll sum = dp[0] = 0;
    		for (int i = 1; i <= n; i++)
    		{
    			sum += a[i].l;
    			dp[i] = max(dp[i - 1], sum) + a[i].r;
    		}
    		cout << dp[n]<<endl;
    	}
    	return 0;
    }

[1257.png]: /images/20220526/e4365615fa8e4dcdb07ecd5d41ab090c.png
[https_cnyali-lk.com_queen]: https://cnyali-lk.com/queen/