思想 : 1 优化:题意是覆盖点,将区间看成 (l,r)转化为( l-1,r) 覆盖区间

2 核心:dp[i]  覆盖从1到i区间的最小花费

        dp[a[i].r]=min (dp[k])+a[i]s;  l-1=<k<=r-1

        (可我总是想着从后到前,从 前到后反而更好理解)

   3  离散区间---使用线段树求区间最值  时间复杂度O(nlogn)

ps (一定忍住不看别人的代码,继续加油)

 #include <bits/stdc++.h>
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
using namespace std;
typedef long long LL;
struct node {
LL l,r,s;
bool operator < (const node& t) const {
return r<t.r;
}
};
const int N=2e5+;
const int MAX=0x3f3f3f3f;
node a[N];
LL b[N]; int cnt;
int tree[N*];
int n; LL M,E;
LL ans;
inline void pushup (int rt) {
tree[rt]=min (tree[rt*],tree[rt*+]);
}
inline int mapp (LL x) {
return lower_bound(b+,b++cnt,x)-b;
}
void update (int p,int k,int l,int r,int rt) {
if (l==r) {
tree[rt]=min (k,tree[rt]);
return ;
}
int m=(l+r)/;
if (p<=m) update (p,k,lson);
else update (p,k,rson);
pushup(rt);
return ;
}
int query (int L,int R,int l,int r,int rt) {
if (l>=L&&r<=R) return tree[rt];
if (l>R||r<L) return MAX;
int m=(l+r)/;
return min (query(L,R,lson),query(L,R,rson));
}
int main ()
{
while (~scanf ("%d %lld %lld",&n,&M,&E)) {
cnt=;
for (int i=;i<=n;i++) {
scanf ("%lld %lld %lld",&a[i].l,&a[i].r,&a[i].s);
a[i].l--;
b[++cnt]=a[i].l; b[++cnt]=a[i].r;
}
sort (b+,b++cnt); cnt=;
for (int i=;i<=*n;i++)
if (b[i]!=b[cnt])
b[++cnt]=b[i]; if (b[]!=M-||b[cnt]!=E) ans=-;
else {
memset (tree,0x3f,sizeof(tree));
sort (a+,a++n);
update (,,,cnt,);
for (int i=;i<=n;i++) {
int r=mapp(a[i].r);
int l=mapp(a[i].l);
int tmp=query (l,r,,cnt,);
update (r,tmp+a[i].s,,cnt,);
}
ans=query (cnt,cnt,,cnt,);
if (ans==MAX) ans=-;
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. 提交本地项目到github服务器
  2. 转载自lanceyan: 一致性hash和solr千万级数据分布式搜索引擎中的应用
  3. 页面可见生Page Visibility
  4. day9---paramiko ssh ftp
  5. Python的高级特性6:使用__slots__真的能省很多内存
  6. Jquery 在页面加载后执行的几种方式
  7. 关于JavaScript是否会阻塞图片加载
  8. jquery插件formValidator的ajaxValidator传参数问题
  9. Lombok(1.14.8) - @Getter, @Setter, @ToString, @EqualsAndHashCode &amp; @Data
  10. 用USB安装Linux系统(centos7)
  11. eclipse下配置安装ssm图文教程(web版)
  12. Map的几种取值方法
  13. 计蒜客 方程的解数 dfs
  14. Linux简单配置SendMail发送邮件
  15. 远程升级云服务器系统 CentOS 6.x 至 CentOS 7.x
  16. oracle中实现当前月减少或增加N个月
  17. 缓存数据库-redis数据类型和操作(hash)
  18. 以太网基础知识0(UDP和TCP有什么区别)
  19. System.map
  20. linux 同步IO: sync、fsync与fdatasync

热门文章

  1. 通过配置hosts.allow和hosts.deny文件允许或禁止ssh或telnet操作
  2. Java反序列化修复方案
  3. vm安装diagram
  4. Oracle多个字段如何合并成一个字段显示
  5. sqlcipher 数据库解密
  6. learning at command AT+CSUB
  7. java字符串根据空格截取并存进ArrayList,并在每个元素前后加上/
  8. bzoj2045
  9. poj1226
  10. 四:(之一和之二) docker架构和底层技术分析(C/S架构)