P4644 [Usaco2005 Dec]Cleaning Shifts 清理牛棚

时间：2023-03-08 19:38:25

P4644 [Usaco2005 Dec]Cleaning Shifts 清理牛棚

你有一段区间需要被覆盖（长度 <= 86,399）

现有 \(n \leq 10000\) 段小线段， 每段可以从 \(l_{i}\) 到 \(r_{i}\) 花费为 \(s_{i}\)

求覆盖整个区间的最小花费

错误日志： 初始化时应该是 \(dp[L - 1]\) 为 \(0\) 而不是 \(dp[1]\) 为 \(0\) ， 因为只需要覆盖 \([L, R]\)

Solution

设 \(dp[n]\) 表示从起点覆盖到 \(n\) 的最小花费

我们将小线段按照右端点升序排序， 满足无后效性

对于第 \(i\) 个线段， 有状态转移方程：$$dp[r_{i}] = min(dp[r_{i}], \min_{l_[i] - 1 \leq k < r_{i}}dp[k] + s_{i})$$

其含义为： 从第 \(i\) 段线段的起点开始选择上一个终点的最小值， 这样可以使线段相交（来保证无空白）， 更新此线段能覆盖的终点

然后发现我们需要区间查询最小值和单点修改

为啥是单点修改不是区间修改呢？ 当两个线段相交， 一定有 \(l_{x} \leq r_{y}\)

所以只需要在线段终点处单点修改即可

初始化 \(dp[L - 1]\) 为零

因为需要线段树维护， 尽量把起点设为 \(1\) 防止各种奇怪的错误， 本题所有位置点坐标 $ + 2$

还要注意处理一下超出 \([L, R]\) 的线段

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int minn = 166419, INF = 1e9;

int num, L, R;

struct Node{

	int l, r, s;

	}I[minn];

bool cmp(Node a, Node b){return a.r < b.r;}

#define lid (id << 1)

#define rid (id << 1) | 1

int dp[minn];

struct seg_tree{

	int l, r;

	int min;

	}tree[minn << 2];

void pushup(int id){tree[id].min = min(tree[lid].min, tree[rid].min);}

void build(int id, int l, int r){

	tree[id].l = l, tree[id].r = r;

	if(l == r){

		tree[id].min = dp[l];

		return ;

		}

	int mid = (l + r) >> 1;

	build(lid, l, mid), build(rid, mid + 1, r);

	pushup(id);

	}

void update(int id, int val, int l, int r){

	if(tree[id].l == l && tree[id].r == r){

		tree[id].min = val;

		return ;

		}

	int mid = (tree[id].l + tree[id].r) >> 1;

	if(mid < l)update(rid, val, l, r);

	else update(lid, val, l, r);

	pushup(id);

	}

int query(int id, int l, int r){

	if(tree[id].l == l && tree[id].r == r)return tree[id].min;

	int mid = (tree[id].l + tree[id].r) >> 1;

	if(mid < l)return query(rid, l, r);

	else if(mid >= r)return query(lid, l, r);

	else return min(query(lid, l, mid), query(rid, mid + 1, r));

	}

int main(){

	num = RD(), L = RD() + 2, R = RD() + 2;//保证线段树左端点是1

	REP(i, 1, R)dp[i] = INF;

	dp[L - 1] = 0;

	build(1, 1, R);

	REP(i, 1, num){

		I[i].l = RD() + 2;

		I[i].r = RD() + 2;

		I[i].s = RD();

		I[i].l = I[i].l < L ? L : I[i].l;//处理一下超出范围的

		I[i].r = I[i].r > R ? R : I[i].r;

		}

	sort(I + 1, I + 1 + num, cmp);

	REP(i, 1, num){

		int minn = query(1, I[i].l - 1, I[i].r);

		//printf("minn=%d\n", minn);

		dp[I[i].r] = min(dp[I[i].r], minn + I[i].s);

		update(1, dp[I[i].r], I[i].r, I[i].r);

		}

	//REP(i, L - 1, R)printf("dp[%d]=%d\n", i - 2, dp[i]);

	if(dp[R] == INF){puts("-1");return 0;}

	printf("%d\n", dp[R]);

	return 0;

	}

相关文章