挺好的dp题，tsx推荐XD
首先可以发现如果两个三角形有交肯定不优，于是我们考虑按照\(x \leq i\)的顺序dp
设\(dp_i\)表示\(x \leq i\)的点全覆盖的最小贡献
容易得到转移:
\[dp_i = \min_{j=1}^{i-1}{(dp_j+j-i+\sum_{l=1}^{n}{(c_l*[j \leq x_l \leq i \& y_l \leq k-i])})}
\]
用线段树优化即可做到\(O(nlogn)\)
CF1842E
发布时间 2023-08-19 09:52:19作者: FOX_konata