首页 > 其他分享 >AT_awtf2024_c Fuel

AT_awtf2024_c Fuel

时间:2024-09-30 17:02:58浏览次数:6  
标签:awtf2024 cur int back dv Fuel 我们 define

dp 好题。

直接考虑不好考虑,但我们有显然的转化,我们并不会多加毫无意义的油。所以我们要加的油是 \(l-2C\),那么现在要求我们在每一时刻油不小于 \(0\),并最小化距离。

发现不太好贪心,考虑 dp。如果我们到了一个加油站,我们一定会将当前的油给加满至 \(C\),除非已经没必要了,但这并不重要。那么状态就呼之欲出,设 \(f_{i,j}\) 表示到了第 \(i\) 个站,与当前类型不同的油量为 \(j\),然后考虑转移。

1.如果下一个站类型不等于当前站类型,我们将会先消耗下一站类型的油,因为我们马上就能够加油了,那么转移将会是 \((i,x)\rightarrow (j,\min(C,x+C-a))\)。

2.如果下一站类型与当前站相同,我们将会先消耗当前类型的油,实在不行再消耗不同类型的油,那么转移是 \((i,x)\rightarrow(j,x-\max(0,a-C))\)。

其中 \(a\) 是距离,考虑继续优化。

首先,手玩一下路径轨迹,直觉上告诉我们往回走是不优的,但是往回走又是存在意义的,为什么呢?因为当相邻两站类型不同时,我们来回走可以增加油量(可以手玩一下),具体的,如果我们在 \(i\) 站,我们走到 \(i-1\) 使得 \(x\) 增加了 \(C-a\),又从 \(i-1\) 到 \(i\) 使得 \(x\) 增加 \(C-a\),这样算下来一共用了 \(2a\) 的代价,使得 \(x\) 增加了 \(2(C-a)\),显然如果 \(a\ge C\) 是不优的。

这样,我们整理一下转移:

\[f_{i+1,j+C-a}=f_{i,j} \]

\[f_{i+1,j+2(C-a)}=f_{i+1,j}+2a \]

实现时我们先转移前者,再转移后者即可。

我们需要继续优化,因为 \(C\) 太大了。我们仔细观察这个 dp,看它长成什么样子。首先发现显然的单调性,我们用二元组表示 \(f_i\) 的每个信息,即 \((j,f_{i,j})\)。也就是说 \(j\) 越大,那么 \(f_{i,j}\) 就越大,并且我们将存在若干个连续段,且是优美的等差数列!\(j\) 的公差为 \(2(C-a)\),\(f_{i,j}\) 的公差为 \(2a\)。我们发现 dp 数组只会有 \(\mathcal{O}(n)\) 种段,对于第一类转移我们可以集体转移,具体的,我们可以记 \(tag\) 表示每个状态的偏移量,而如果 \(tag\) 减小,自然某些小的 \(j\) 会被丢出去,如果 \(tag\) 增加,就会使得 \(j\) 超过 \(C\),当 \(j\) 超过 \(C\) 时,相当于一个新的开始,我们不得不以每个站为起点做一次 dp,前面可以用一个双端队列进行维护,那么反复横跳的转移如何实现呢?我们发现,如果其 \(f_{i,j}\) 的公差如果大于当前的 \(2a\),显然我们可以丢出去,然后从第一个公差小于当前 \(2a\) 的状态开始转移即可,如果全部弹出那么就从初始第一个开始。

至于为啥我们要维护那么多 \(2a\) 而不是维护最小的,因为 \(C\) 是有限的,在很划算的地方横跳也顶多只能赚到 \(C\)。

于是我们就做完了!时间复杂度 \(\mathcal{O}(n^2)\),代码:

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define pii pair <int, int>
#define eb emplace_back
#define inf 1000000000
#define id(x, y) n * (x - 1) + y
#define ls p << 1
#define rs ls | 1
using namespace std;
constexpr int N = 5e3 + 5, M = (1ll << 31) - 1, P = 1e9 + 7;
constexpr double PI = acos (-1.0);
inline int rd () {
  int x = 0, f = 1;
  char ch = getchar ();
  while (! isdigit (ch)) {
    if (ch == '-') f = -1;
    ch = getchar ();
  }
  while (isdigit (ch)) {
    x = (x << 1) + (x << 3) + ch - 48;
    ch = getchar ();
  }
  return x * f;
}
int qpow (int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = x * x % P) if (y & 1) ret = ret * x % P;
  return ret;
}
void add (int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
int n, m, C;
int x[N], f[N];
int t[N];
class node {
  public:
    int l, r, v, d, dv;
} ;
signed main () {
  // freopen ("1.in", "r", stdin);
  // freopen ("1.out", "w", stdout);
  for (int T = rd (); T; -- T) {
    n = rd (), m = rd (), C = rd ();
    rep (i, 1, n + 1) f[i] = 1e18;
    rep (i, 1, n) x[i] = rd ();
    rep (i, 1, n) t[i] = rd ();
    x[0] = 0, x[n + 1] = m;
    rep (i, 0, n) x[i] = x[i + 1] - x[i];
    int ans = 1e18;
    rep (i, 0, n) {
      if (f[i] == 1e18) continue;
      deque <node> q;
      int cur = 0;
      q.push_back ((node) {C, C, f[i], 0, 0});
      rep (j, i, n) {
        cur += t[j] == t[j + 1] ? - max (0ll, x[j] - C) : C - x[j];
        while (! q.empty ()) {
          node& t = q[0];
          if (t.r + cur < 0) q.pop_front ();
          else {
            if (t.l + cur < 0) {
              int k = (- t.l - cur + t.d - 1) / t.d;
              t.l += k * t.d, t.v += k * t.dv;
            } break;
          }
        }
        while (! q.empty ()) {
          node& t = q.back ();
          if (t.l + cur > C) f[j + 1] = min (f[j + 1], t.v), q.pop_back ();
          else {
            if (t.r + cur > C) {
              int k = (C - t.l - cur) / t.d + 1;
              f[j + 1] = min (f[j + 1], t.v + k * t.dv);
              t.r = t.l + (k - 1) * t.d;
            } break;
          }
        }
        if (q.empty ()) break;
        if (t[j] == t[j + 1] || C <= x[j]) continue;
        int v = q[0].v, l = q[0].l;
        for (; (! q.empty ()) && q.back ().dv >= x[j] * 2; q.pop_back ()) ;
        if (q.size ()) {
          node t = q.back ();
          if (! t.d) v = t.v, l = t.l;
          else {
            l = t.r;
            v = t.v + (l - t.l) / t.d * t.dv;
          }
        }
        int d = 2 * (C - x[j]), dv = 2 * x[j];
        int k = (C - cur - l) / d + 1;
        f[j + 1] = min (f[j + 1], v + dv * k);
        q.push_back ((node) {l, l + (k - 1) * d, v, d, dv});
      }
      if (! q.empty ()) ans = min (ans, q[0].v);
    } ans = min (ans, f[n + 1]);
    if (ans == 1e18) puts ("-1"); else printf ("%lld\n", max (0ll, ans + m - C * 2));
  }
}

标签:awtf2024,cur,int,back,dv,Fuel,我们,define
From: https://www.cnblogs.com/lalaouyehome/p/18442159

相关文章

  • AWTF2024A Moving Slimes 题解
    发现史莱姆不合并也不会影响答案,所以就不用考虑合并了。这样处理之后,史莱姆的移动可以看作是受到与其不在同一位置的史莱姆的吸引所完成的,每只史莱姆可以给其他史莱姆一个单位的吸引力。因为每只史莱姆提供的吸引力是恒定的,所以考虑把吸引力放在它们的重心上,设\(pre_i\)表示坐......
  • 6.1.1 FUEL单无人机自主搜索
    6.1.1单无人机自主搜索参考教程:HKUST-Aerial-Robotics/FUEL:AnEfficientFrameworkforFastUAVExploration(github.com)1.查看系统环境要运行本仿真程序,需要保证当前环境为ubuntu18.04+ros-melodic-desktop-full查看ubuntu版本:rosnoetic@rosnoetic-VirtualBo......
  • ABC 320F Fuel Round Trip
    题意在坐标轴上给定N个点,坐标依次为x1,x2,...,xn,你需要从原点前往xn并且实现往返,其中从第一个点到第N-1个点上有加油站,其中第i个加油站可以花费p[i]购买f[i]升汽油,汽油的上限为H升,每行驶一单位距离需要花费一升汽油。在全部过程中每个加油站最多使用一次,判断是否可以完成行程并......
  • [ABC320F]FuelRoundT
    [ABC320F]FuelRoundTrip这道题我们首先观察数据范围,发现\(n,h\le300\),于是就可以围绕它想一个三次方的复杂度。这个数据范围,一般明摆着就是DP,所以我先往DP方向思考。首先思考如果只要一趟的情况,发现十分简单,令\(dp_{i,j}\)表示到达第\(i\)个油站,加完/不加后剩余的......
  • [ABC320F] Fuel Round Trip 题解
    题意在坐标轴上给定\(N\)个点,坐标依次为\(X_1,X_2,\cdots,X_N\),你需要从原点前往\(X_N\)并折返,其中在第\(1\)个到第\(N-1\)个点上有加油站,其中第\(i\)个加油站可以花费\(P_i\)购买\(F_i\)升汽油,汽油持有上限为\(H\)升,每行驶一单位距离需要花费一升汽油。在......
  • [LeetCode] 2477. Minimum Fuel Cost to Report to the Capital
    Thereisatree(i.e.,aconnected,undirectedgraphwithnocycles)structurecountrynetworkconsistingof n citiesnumberedfrom 0 to n-1 andexactl......
  • Kotlin实战之Fuel的高阶函数
    ​​Fuel​​​是一个用Kotlin写的网络库,与OkHttp相比较,它的代码结构比较简单,但是它的巧妙之处在于充分利用了​​Kotlin的语言特性​​,所以代码看上去干净利落。OkH......
  • 871. Minimum Number of Refueling Stops
    Acartravelsfromastartingpositiontoadestinationwhichis target mileseastofthestartingposition.Therearegasstationsalongtheway.Thegasst......