原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round4-B.html
题目传送门 - https://www.nowcoder.com/acm/contest/142/B
题意
给定 $n$ 条带权线段，第 $i$ 条线段的左右端点坐标分别 $x_i,y_i$ ，权值为 $w_i$ ，坐标范围是 $[1,m]$ 。
现在让你从这 $n$ 条线段中选择一些线段，要求这些线段能覆盖 $[1,m]$ 中的任何一个整点。
定义 $f(x)$ 为当前方案中覆盖到坐标 $x$ 的线段的权值和。
问：对于所有的选择线段的方案，$\max(f(x)|x\in [1,m])$ 的最小值为多少。
多组数据。
$n,m\leq 2000,w_i\leq 1000,\sum n\leq 20000$
题解
讲题人说要线段树？？
直接 $O(nm)$ dp 啊。
首先我们证明两个结论：
1. 选出来的线段不存在包含关系。——如果这样的话删掉被包含的那条显然更好
2. 任何一个点最多被两个线段覆盖。——如果有三条覆盖同一个点，那么一定可以删除其中一条，并满足剩下的线段仍然覆盖所有点。
这两个性质十分优秀！于是我们就可以 dp 了。
我们先把所有的线段按照右端点从小到大排序。
记 $dp_{i,j}$ 表示最右端的一条线段为 $i$ ，上一个线段的结尾的坐标不大于 $j$ 时，$\max(f(x)|x\in [1,m])$ 的最小值 。
那么，我们对于每一个 $i$ 首先求出所有 上一个线段的结尾的坐标等于 $j$ 时 的 dp 值，然后搞一搞前缀 $\min$ 即可。
时间复杂度 $O(nm)$ 。
代码
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
const int N=2005;
int n,m,dp[N][N];
struct Segment{
int L,R,w;
}a[N];
bool cmp(Segment a,Segment b){
return a.R<b.R;
}
int main(){
for (int T=read();T;T--){
n=read(),m=read();
for (int i=1;i<=n;i++)
a[i].L=read(),a[i].R=read(),a[i].w=read();
sort(a+1,a+n+1,cmp);
for (int i=0;i<=n;i++)
for (int j=0;j<=m;j++)
dp[i][j]=i==0?0:1e8;
a[0].R=0;
int ans=dp[1][1];
for (int i=1;i<=n;i++){
for (int j=0;j<i;j++){
if (a[j].R+1<a[i].L||a[i].R<=a[j].R)
continue;
int v=dp[j][a[i].L-1];
if (a[j].R>=a[i].L)
v=max(v,a[i].w+a[j].w);
else if (a[j].R+1==a[i].L)
v=max(v,a[i].w);
dp[i][a[j].R]=min(dp[i][a[j].R],v);
}
for (int j=1;j<=m;j++)
dp[i][j]=min(dp[i][j],dp[i][j-1]);
if (a[i].R==m)
ans=min(ans,dp[i][m]);
}
printf("%d\n",ans>=1e8?-1:ans);
}
return 0;
}