题解 P4644 【[Usaco2005 Dec]Cleaning Shifts 清理牛棚】
追梦_Chen
·
·
题解
这里推荐一种数据结构优化DP的写法,
我们先把该题目转换成一个带权值的线段覆盖问题：
给定一个区间[l,r]，接着再给n条带权值的边，边的左端点为a_i, 右端点为b_i,使用该边的代价为c_i
我们用f[x]表示覆盖[l,x]的最小代价
排序，按 b_i 的值升序排序，从 b_1 到 b_n 遍历一遍，
我们能推出一个状态转移方程:f[b_i]=min ({f[x]},f[b_i])+c_i
# 证明
我们设上一段的左端点为p,右端点为q，如果区间能够被完全覆盖那么$a_{i-1}$一定小于等于q，而上一段的 f[q] 已经求出来了，根据无后效性，数组f在区间$[a_i-1,b_i]$的最小值就能由f[q]转移过来了；如果不能覆盖，该区间的最小值会是一个无穷大的值，输出-1，程序结束。
# 技巧
```cpp
如果我们直接朴素（暴力）的来找数组f在区间a[i]-1到b[i]的最小值的话，肯定超时，于是我们可以用线段树来实现单点修改，区间查询的功能~
```
# 放代码
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn=251000;
int n,l,r;
int f[maxn];
struct node{
int a,b,c;
}cow[maxn];
struct tree{
int l,r,dat;
}t[maxn*4];
bool cmp(node a,node b){
return a.b<b.b;
}//按b的值升序排序
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){
t[p].dat=f[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
}//建树
void change(int p,int x,int v){
if(t[p].l==t[p].r){
t[p].dat=v;
return;
}
int mid=(t[p].l+t[p].r)/2;
if(x<=mid) change(p*2,x,v);
else change(p*2+1,x,v);
t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
}//单点修改
int ask(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r){
return t[p].dat;
}
int mid=(t[p].l+t[p].r)/2;
int val=1<<30;
if(l<=mid) val=min(val,ask(p*2,l,r));
if(r>mid) val=min(val,ask(p*2+1,l,r));
return val;
}//区间查询
int main(){
scanf("%d %d %d",&n,&l,&r);
for(int i=1;i<=n;i++){
scanf("%d %d %d",&cow[i].a,&cow[i].b,&cow[i].c);
}
sort(cow+1,cow+n+1,cmp);//按b的值升序排序
memset(f,0x3f,sizeof(f));
f[l]=0;//从起点到起点，花费当然是0了
build(1,l,r);
for(int i=1;i<=n;i++){
f[cow[i].b]=min(f[cow[i].b],ask(1,cow[i].a-1,cow[i].b)+cow[i].c);
//找区间[ a[i]-1,b[i] ] 的最小值
change(1,cow[i].b,f[cow[i].b]);
if(cow[i].b>=r){
if(f[cow[i].b]==0x3f3f3f3f){
printf("-1"); //不能完全覆盖
}else{
printf("%d",f[cow[i].b]);
} //覆盖到了r直接输出最小值，程序结束
return 0;
}
}
return 0;
}
```