AT_awtf2024_c Fuel

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));}
}