UVALive 3983 (单调队列优化dp)

青旅半醒 2021-12-14 04:15 291阅读 0赞

## 题意：有一个机器人要捡n个垃圾到垃圾桶(0, 0)里，给出了机器人最多可以捡多重的垃圾c，然后给出了n个垃圾的位置和重量，机器人只能按给出的顺序捡垃圾，然后一起扔到垃圾桶里，问把所有垃圾清理完机器人行走的最短距离。 ##

## 分析：《训练指南》P73。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 100000 + 10;
    
    int x[maxn], y[maxn];
    int total_dist[maxn], total_weight[maxn], dist2origin[maxn];
    int q[maxn], d[maxn];
    
    int func(int i) {
      return d[i] - total_dist[i+1] + dist2origin[i+1];
    }
    
    main() {
      int T, c, n, w, front, rear;
      scanf("%d", &T);
      while(T--) {
        scanf("%d%d", &c, &n);
        total_dist[0] = total_weight[0] = x[0] = y[0] = 0;
        for(int i = 1; i <= n; i++) {
          scanf("%d%d%d", &x[i], &y[i], &w);
          dist2origin[i] = abs(x[i]) + abs(y[i]);
          total_dist[i] = total_dist[i-1] + abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);
          total_weight[i] = total_weight[i-1] + w;
        }
        front = rear = 1;
        for (int i = 1; i <= n; i++) {
          while (front <= rear && total_weight[i] - total_weight[q[front]] > c) front++;
          d[i] = func(q[front]) + total_dist[i] + dist2origin[i];
          while (front <= rear && func(i) <= func(q[rear])) rear--;
          q[++rear] = i;
        }
        printf("%d\n", d[n]);
        if(T > 0) printf("\n");
      }
      return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，291人围观）

还没有评论，来说两句吧...

相关阅读

相关 AcWing 289. 环路运输【环形DP + 单调队列优化】

一条环形公路旁均匀地分布着N座仓库，编号为1~N，编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 dist(i,j)=min⁡(|i-j|,N-|i-j|)，也就...

痛定思痛。/ 2024年04月19日 11:13/ 0 赞/ 73 阅读

相关 uva3983（dp+单调队列）捡垃圾的机器人

例题 31 捡垃圾的机器人（ Robotruck, SWERC 2007, LA 3983 ）有 n 个垃圾，第 i 个垃圾的坐标为（ x i ， y i ）

╰+哭是因爲堅強的太久メ/ 2024年02月17日 23:23/ 0 赞/ 65 阅读

相关单调队列优化总结

单调队列一般只能优化一类问题，也即维护长度为k的区间最值问题。使用hh和tt表示队头和队尾，当hh = 0, tt = -1表示队列为空，当hh和tt都等于0的时候表示队列有一

电玩女神/ 2022年08月28日 08:58/ 0 赞/ 200 阅读

相关 UVA 12170 Easy Climb(dp+单调队列优化)

题意：给出一个序列，首尾不可改变，要求你使序列满足相邻2个|x\_i - x\_(i-1)| <=d，改变的代价就是两数相减绝对值，问最小代价。分析：区间dp

向右看齐/ 2021年12月16日 23:34/ 0 赞/ 259 阅读

相关 [单调队列优化DP]JZOJ 3128 跳格子

Description 奶牛们正在回味童年，玩一个类似跳格子的游戏，在这个游戏里，奶牛们在草地上画了一行N个格子，(3 <=N <= 250,000)，编号为1..N。

以你之姓@/ 2021年12月16日 01:09/ 0 赞/ 303 阅读

相关 UVALive 3983 (单调队列优化dp)

题意：有一个机器人要捡n个垃圾到垃圾桶(0, 0)里，给出了机器人最多可以捡多重的垃圾c，然后给出了n个垃圾的位置和重量，机器人只能按给出的顺序捡垃圾，然后一起扔到垃圾桶里，

青旅半醒/ 2021年12月14日 04:15/ 0 赞/ 292 阅读

相关 LA 4327 Parade（单调队列优化dp）

题意：F城由n+1个横向路和m+1个竖向路组成。你的任务是从最南边的路走到最北边的路，使得走过的路上的高兴值和最大（高兴值可能为负值）。同一段路不能经过两次，且不能从北往南走

Dear 丶/ 2021年11月16日 23:36/ 0 赞/ 310 阅读

相关 Codeforces 445A Boredom（DP+单调队列优化）

题目链接：[http://codeforces.com/problemset/problem/455/A][http_codeforces.com_problemset_pro

柔光的暖阳◎/ 2021年10月23日 09:41/ 0 赞/ 398 阅读

相关 AcWing 1089. 烽火传递【单调队列优化DP 】 C++详细题解

单调队列优化DP -------------------- 题目烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天

男娘i/ 2021年07月25日 02:34/ 0 赞/ 464 阅读

相关 AcWing 1087. 修剪草坪【单调队列优化DP】C++详细题解

单调队列优化DP -------------------- 题目在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。现在

桃扇骨/ 2021年07月24日 23:31/ 1 赞/ 429 阅读