离散化写挫了就wa了n发。。
先按照右端点排序，设dp[i]为铺满1到i的最小价值，注意是铺满，那么就可以在这里更新dp[r[i]]=min(dp[j])+v[i] l[i]<=j<=r[i]，注意这里有一个-1，对于左端点来说，因为如果两个线段相邻二不相交，比如(1,2)(3,4)，这样其实也是可以的。这里的话，如果直接把端点离散化，就会导致后面的操作很复杂，因为要考虑相邻中间有没有空（我也是这么错的），所以不如直接在一开始读入左端点的时候就给他-1，这样之后就不用什么多余的操作了，直接每次线段树查询最小值即可。 继续阅读“[DP][线段树][离散化][细节][坑] XDOJ 1324”