Memory题解(线段树优化DP)

发布时间 2023-09-05 22:23:59作者: 傻阙的缺

传送门

简要题意:

给定 \(m\) 条线段,每条线段由四个正整数参数 \(l_i,r_i,c_i,w_i\) 描述,其中 \(l_i,r_i\) 是这条线段的端点,\(c_i\) 是这条线段的种类,\(w_i\) 是这条线段的权值。

你需要选出一些线段,满足以下条件且权值总和最高。

  • 对于任意两条不同的线段 \(i,j\),满足 \(c_i = c_j\)\([l_i,r_i]\cap[l_j,r_j]=\varnothing\)

先将 \(l,r,c\) 离散化,再将 \(l,r,c\) 完全一样的线段完全合并。

然后以 \(r\) 为第一关键字,\(l\) 为第二关键字,进行排序