[文章目录]
Description
求一个大区间由小区间的最小代价的全覆盖。
dp[i]表示到i这一位都覆盖完的最小代价。发现这个东西应当为后缀最小值，拿树状数组维护一下就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,e,f[101000];
struct node{int t1,t2,w;}a[11000];
inline bool cmp(const node x,const node y){return x.t1<y.t1;}
void fix(int x,int y)
{
while(x>0) f[x]=min(f[x],y),x-=-x&x;
}
int query(int x)
{
if(!x) return 0;
int re=1<<30;
while(x<=e) re=min(re,f[x]),x+=-x&x;
return re;
}
int main()
{
scanf("%d%d%d",&n,&m,&e); m++,e++;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].t1,&a[i].t2,&a[i].w);
a[i].t1++; a[i].t2++;
}
sort(a+1,a+n+1,cmp);
memset(f,0x3f,sizeof(f));
fix(m-1,0);
for(int i=1;i<=n;i++)
{
int tmp=query(a[i].t1-1);
tmp+=a[i].w;
fix(a[i].t2,tmp);
}
int ans=query(e);
if(ans==0x3f3f3f3f) puts("-1");
else printf("%d\n",ans);
return 0;
}