首先 一个点最多被两个区间覆盖,
若按常规套路设 表示处理到前 个区间覆盖 的最小代价,
转移:
如下图, 如果从 转移过来, 会 “忽略” 的存在, 导致答案变为 ,
在转移时并不知道转移的来源会与哪些区间重合, 导致并不知道这个区间会与哪些区间重合,
换就话说, 转移的来源并不纯净,
我们需要转移的时候使得两个区间相交的区域没有别的区间存在, 于是可以想到多设一维去保证上述条件 .
设 表示处理到第 个区间, 被覆盖一次的 最大值,
假设从第 个区间转移而来, 前提是 , 分情况讨论,
- ,
- ,
#include<bits/stdc++.h>
#define reg register
int read(){
char c;
int s = 0, flag = 1;
while((c=getchar()) && !isdigit(c))
if(c == '-'){ flag = -1, c = getchar(); break ; }
while(isdigit(c)) s = s*10 + c-'0', c = getchar();
return s * flag;
}
const int maxn = 3005;
const int inf = 0x3f3f3f3f;
int N;
int M;
int F[maxn][maxn];
struct Intval{ int l, r, w; } A[maxn];
bool cmp(Intval a, Intval b){ return a.r < b.r; }
void Work(){
N = read(), M = read();
for(reg int i = 1; i <= N; i ++) A[i].l = read(), A[i].r = read(), A[i].w = read();
std::sort(A+1, A+N+1, cmp);
for(reg int i = 1; i <= N; i ++){
for(reg int j = 0; j <= M; j ++) F[i][j] = inf;
for(reg int j = i; j >= 0; j --){
if(A[j].r < A[i].l-1) break ;
F[i][A[j].r] = std::min(F[i][A[j].r], std::max(F[j][A[i].l-1], (A[j].r==A[i].l-1?0:A[j].w) + A[i].w));
}
for(reg int j = 1; j <= M; j ++) F[i][j] = std::min(F[i][j], F[i][j-1]);
}
int Ans = inf;
for(reg int i = N; i >= 1; i --){ if(A[i].r < M) break ; Ans = std::min(Ans, F[i][A[i].r]); }
printf("%d
", Ans==inf?-1:Ans);
}
int main(){ int T = read(); while(T --) Work(); return 0; }