100 #P1377. *【动态规划:状态设计DP】不重叠线段的最小长度和[scy](待验证)
*【动态规划:状态设计DP】不重叠线段的最小长度和[scy](待验证)
【题意】
数轴上有 条线段 ,选出若干不重叠线段,且任意一条不选的线段必至少与一条所选线段有重叠,求所选线段长度和最小。
【输入格式】
第一行一个整数 。
下来 行,每行两个整数 (),描述线段的起点和末端。
【输出格式】
一个整数,表示最小长度和。
3
1 3
7 8
2 5
3
数轴上有 n 条线段 [xi,yi],选出若干不重叠线段,且任意一条不选的线段必至少与一条所选线段有重叠,求所选线段长度和最小。
第一行一个整数 n(1≤n≤2×105) 。
下来 n 行,每行两个整数 xi,yi(0≤xi≤yi≤1010),描述线段的起点和末端。
一个整数,表示最小长度和。
3
1 3
7 8
2 5
3