#PQJ1193x6178. QOJ 1193_6178

    ID: 2565 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:FJOI 2022排序贪心

QOJ 1193_6178

给定实轴上 𝑛 个区间,第 𝑖 个区间为 [ 𝐿 𝑖 , 𝑅 𝑖 ] ( 1 ≤ 𝑖 ≤ 𝑛 )。这 𝑛 个区间的 2 𝑛 个区间端点互不相同。由此可知,这 𝑛 个区间中,任何 2 个区间或其交集为空,或有包含关系。

区间子集问题:对于实轴上给定的区间端点互不相同的 𝑛 个区间 [ 𝐿 𝑖 , 𝑅 𝑖 ] ( 1 ≤ 𝑖 ≤ 𝑛 ),从每个子区间 [ 𝐿 𝑖 , 𝑅 𝑖 ] 中选取一个子区间 [ 𝑙 𝑖 , 𝑟 𝑖 ] ( 𝐿 𝑖 ≤ 𝑙 𝑖 < 𝑟 𝑖 ≤ 𝑅 𝑖 ),使得选出的任何 2 子区间的交集最多只有 1 个点。要求选出的 𝑛 个子区间的长度之和 ∑ 𝑖

1 𝑛 ( 𝑟 𝑖 − 𝑙 𝑖 ) 达到最大。

输入格式

第一行为一个正整数 𝑛 。

接下来每行有两个整数,第 𝑖 + 1 行给出两个整数 𝐿 𝑖 , 𝑅 𝑖 ,表示相应区间为 [ 𝐿 𝑖 , 𝑅 𝑖 ] 。

输出格式

输出计算出的最大子区间的长度和。

样例数据 样例输入 4 1 10 2 3 5 9 6 7 样例输出 7 子任务

测试数据中 10 % 的数据满足 𝑛 ≤ 10 。

测试数据中 40 % 的数据满足 𝑛 ≤ 500 。

测试数据中 100 % 的数据满足 𝑛 ≤ 2 000 。