传送门

题目大意

有一个大区间和n个小区间,每个小区间都有一个代价,求最少付出多少代价可以使得小区间完全覆盖大区间。

分析
为了方便起见我们先将s变为2,其它的位置都对应更改以便后期处理。我们考虑以t1为第一关键字,t2为第二关键字将所有奶牛排序。用dp[i][j]表示考虑到第i只牛,覆盖到点j最少需要多少钱。我们可以将i这一维去掉,则dp[j]=min{dp[j],dp[j'](t1-1<=j'<=t2-1)}。然后进行线段树优化就可以了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const long long inf = 1e12+;
struct node {
long long t1,t2,sum;
};
node wh[];
long long d[];
inline bool cmp(const node x,const node y){
if(x.t1==y.t1)return x.t2<y.t2;
return x.t1<y.t1;
}
inline void build(long long le,long long ri,long long wh,long long pl,long long k){
if(le==ri){
d[wh]=k;
return;
}
long long mid=(le+ri)>>;
if(mid>=pl)build(le,mid,wh<<,pl,k);
else build(mid+,ri,wh<<|,pl,k);
d[wh]=min(d[wh<<],d[wh<<|]);
return;
}
inline long long q(long long le,long long ri,long long wh,long long x,long long y){
if(le>=x&&ri<=y){
return d[wh];
}
long long mid=(le+ri)>>,ans=inf;
if(mid>=x)ans=min(ans,q(le,mid,wh<<,x,y));
if(mid<y)ans=min(ans,q(mid+,ri,wh<<|,x,y));
return ans;
}
int main(){
long long n,s,t,i,j,k;
scanf("%lld%lld%lld",&n,&s,&t);
for(i=;i<=n;i++){
scanf("%lld%lld%lld",&wh[i].t1,&wh[i].t2,&wh[i].sum);
wh[i].t1+=;
wh[i].t2+=;
wh[i].t1-=s;
wh[i].t2-=s;
}
t=(t-s)+,s=;
build(,t,,,);
for(i=s;i<=t;i++)
build(,t,,i,inf);
sort(wh+,wh+n+,cmp);
for(i=;i<=n;i++){
long long x=min(q(,t,,wh[i].t2,wh[i].t2),
q(,t,,wh[i].t1-,wh[i].t2-)+wh[i].sum);
build(,t,,wh[i].t2,x);
}
long long x=q(,t,,t,t);
if(x>=inf)x=-;
printf("%lld\n",x);
return ;
}

最新文章

  1. 基于Node.js实现一个小小的爬虫
  2. Bzoj3894 文理分科
  3. 在本地测试一次成功的AJAX请求
  4. org.hibernate.HibernateException: No Session found for current thread
  5. 第一篇随笔!!!THE FIRST BLOOD!!!
  6. isNaN() 确认是否是数字
  7. Ember Charts – 基于 Ember &amp; D3 的图表库
  8. [POJ3264]Balanced Lineup(线段树,区间最值差)
  9. 配置mysql允许远程连接
  10. http://codeforces.com/contest/349
  11. linux 基本命令2
  12. @Override is not allowed when implementing interface method
  13. 大学?做码农?做project师?
  14. 第 5 章 网络 - 032 - 学容器必须懂 bridge 网络
  15. UPDATE语句中SET部分列赋值的先后顺序有影响么?
  16. iOS开发--关闭ARC
  17. 关于网站的SYN_RECV(SYN_RECEIVED)***的防范措施
  18. ABP实战--项目结构
  19. 媒体类型(MIME类型)
  20. 基于CSS3自定义发光radiobox单选框

热门文章

  1. (转)轻量级C语言实现的minixml解析库入门教程
  2. CERC2016 爵士之旅 Jazz Journey
  3. centos安装yum源
  4. Excel合并计算
  5. Python collections系列之有序字典
  6. java文本文件读写
  7. 运行flask程序
  8. div 遮罩层 弹窗
  9. 学习SQL Server从在Linux上安装开始
  10. ORACLE增加用户