POJ 3171 Cleaning Shifts(DP+zkw线段树)

时间:2021-04-25 03:42:47

【题目链接】 http://poj.org/problem?id=3171

【题目大意】

  给出一些区间和他们的价值,求覆盖一整条线段的最小代价

【题解】

  我们发现对区间右端点排序后有dp[r]=min(dp[l-1~r-1])+s
  而对于求最小值我们可以用线段树优化

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
const int N=100010;
int T[N*4],n,m,E,M,x,y;
struct data{int l,r,s;}p[N];
bool cmp(data a,data b){return a.r<b.r;}
int main(){
while(~scanf("%d%d%d",&n,&m,&E)){
E=E-m+2;
for(M=1;M<E;M<<=1);
fill(T,T+M+E+1,INT_MAX/2);
T[M+1]=0;
for(int i=0;i<n;i++){
scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].s);
p[i].l=p[i].l-m+2;
p[i].r=p[i].r-m+2;
}sort(p,p+n,cmp);
for(int i=0;i<n;i++){
int t=INT_MAX/2;
x=p[i].l+M-2; y=p[i].r+M;
while(x^y^1>0){
if(~x&1)t=min(t,T[x+1]);
if(y&1)t=min(t,T[y-1]);
x>>=1;y>>=1;
}T[M+p[i].r]=min(T[M+p[i].r],t+p[i].s);
for(x=(M+p[i].r)/2;x;x/=2)T[x]=min(T[x<<1],T[(x<<1)^1]);
}printf("%d\n",T[E+M]==INT_MAX/2?-1:T[E+M]);
}return 0;
}