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