题目

---

思路

考的知识点是线段树+dp。

我们可以按照dp 4步法来一步步推导、

1.dp定义

dp[i]代表[1,i]区间被给出线段覆盖的最小花费

2.状态转移方程

根据dp定义可得当枚举到第x条线,区间为[Lx,Rx],花费为Vx时

dp[Rx]=min(dp[i](i = (Lx - 1) ~ Rx))+Vx

因为当想要覆盖[1,Rx]的区间就必须在覆盖[1,Lx - 1]/[1,Lx]……/[1,Rx]的基础上再加上第x条线段。

而覆盖[1,Lx - 1]/[1,Lx]……/[1,Rx]的最小花费就是(dp[i](i = (Lx - 1) ~ Rx)，再加上第x条线段的花费是Vx。

画个图来理解:

这个时候会有个问题:在这里我们要求min(dp[i](i = (Lx - 1) ~ Rx)，可是如果暴力枚举找min的话时间复杂度O(n*m)会超时,那该怎么办呢?我们可以用线段树(详见详解线段树)来实现查找区间最小值和单点更新(dp在变)的效果。

3.初始化

一个是dp一开始要是无穷大,一个是minv(线段树的那个)也要初始化为无穷大,另外储存线段的数组也要以r从大到小排序(这样才能保证后续枚举线段时dp[i](i = (Lx - 1) ~ Rx是最优的)

4.遍历顺序

显然就是以下标顺序枚举所有线段。

---

代码

#include <bits/stdc++.h>
#define int long long
#define maxn 300000
using namespace std;
int n,m,dp[5000000],minv[5000000];
struct shui
{int l,r,v;
} a[5000000];
bool cmp(shui x,shui y)
{return x.r < y.r;
}
int find(int id,int l,int r,int x,int y)//查找[x,y]区间内的最小值
{if(x <= l && r <= y) return minv[id];int mid = (l + r) / 2,ans = INT_MAX;if(x <= mid) ans = min(ans,find(id * 2,l,mid,x,y));if(y > mid) ans = min(ans,find(id * 2 + 1,mid + 1,r,x,y));return ans;
}
void gexi(int id,int l,int r,int x,int v)//将编号为x的节点的值更改为v
{if(l == r){minv[id] = v;return ;}int mid = (l + r) / 2;if(x <= mid) gexi(id * 2,l,mid,x,v);else gexi(id * 2 + 1,mid + 1,r,x,v);minv[id] = min(minv[id * 2],minv[id * 2 + 1]);
}
signed main()
{scanf("%lld%lld",&n,&m);for(int i = 1; i <= n; i++) scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].v);memset(dp,0x3f,sizeof(dp));memset(minv,0x3f,sizeof(minv));//minv对应的是dpsort(a + 1,a + 1 + n,cmp);for(int i = 1; i <= n; i++){if(a[i].l == 1){if(dp[a[i].r] > a[i].v){dp[a[i].r] = a[i].v;gexi(1,1,maxn,a[i].r,a[i].v);}}else{int t = find(1,1,maxn,a[i].l - 1,a[i].r);if(dp[a[i].r] > (t + a[i].v)){dp[a[i].r] = t + a[i].v;gexi(1,1,maxn,a[i].r,dp[a[i].r]);}}}printf("%lld",dp[m]);return 0;
}