luogu2123 皇后游戏

好题。
网上看到的范围是：\(T \leq 10\)，$ n \leq 50000$， $ a_i,b_i \leq 10^9$。
我们按照贪心惯常的思路考虑交换相邻的两个人。容易发现，对于相邻的两个人，总是后一个人的答案更大一点。而我们的目的，是让两个人中后一个人的答案更小（这样可以让这两个人后面的答案更小）。
设当前在考虑 \(i\) 与\(i+1\)。记前\(i-1\)号的和为\(sum\)。欲使后面的人答案更小一点，假设\(i\)在前是后面的人答案更小一点，则有
\[ \max(\max(sum+a_i,c_{i-1})+b_i, sum+a_i+a_{i+1})+b_{i+1}\]
\[\max(\max(sum+a_{i+1},c_{i-1})+b_{i+1}, sum+a_i+a_{i+1})+b_i\]
前者小于后者。

将它们合并到一个max里头，有
\[ \max(sum+a_i+b_i+b_{i+1}, c_{i-1}+b_i+b_{i+1}, sum+a_i+a_{i+1}+b_{i+1})\]
\[ \max(sum+a_{i+1}+b_i+b_{i+1}, c_{i-1}+b_i+b_{i+1}, sum+a_i+a_{i+1}+b_i)\]
前者小于后者。

发现第二项相同，可以同时抛去。（想不通的话想一想$ \max(a, 1)<\max(b, 1)$是怎么回事就好了）
得到
\[ \max(sum+a_i+b_i+b_{i+1}, sum+a_i+a_{i+1}+b_{i+1})\]
\[ \max(sum+a_{i+1}+b_i+b_{i+1}, sum+a_i+a_{i+1}+b_i)\]
前者小于后者。

同时抛去 \(sum\) 得到
\[ \max(a_i+b_i+b_{i+1}, a_i+a_{i+1}+b_{i+1})\]
\[ \max(a_{i+1}+b_i+b_{i+1}, a_i+a_{i+1}+b_i)\]
前者小于后者。

同时减去$ a_i+a_{i+1}+b_i+b_{i+1}$得到
\[ \max(-a_{i+1}, -b_i)

化开得到
\[ \min(a_i, b_{i+1})<\min(a_{i+1}, b_i)\]
这就是排序条件。
然后就很简单啦qwq。

#include 
#include 
#include 
using namespace std;
struct Node{long long aa, bb;
}nd[50005];
int T, n;
long long dp[50005], sum;
bool cmp(Node x, Node y){return min(x.aa, y.bb)>T;while(T--){scanf("%d", &n);for(int i=1; i<=n; i++)scanf("%lld %lld", &nd[i].aa, &nd[i].bb);sort(nd+1, nd+1+n, cmp);sum = dp[0] = 0;for(int i=1; i<=n; i++){sum += nd[i].aa;dp[i] = max(dp[i-1], sum) + nd[i].bb;}printf("%lld\n", dp[n]);}return 0;
}

转载于:https://www.cnblogs.com/poorpool/p/8059453.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！