F - Hammer 2（ABC273f）

题意

高桥是数轴的起源。高桥想在坐标达到目标X.

此外，还有n墙壁和n锤在数轴上。

在坐标是
Y₁…Y_n

是类型的墙1…n分别。
最初，高桥无法翻墙。
在坐标Z₁…Z_n
​​​
是类型的锤子1 、2 、…,n,分别。
当他用锤子到达一个坐标时，他得到了锤子。
锤子致力于破坏类型相同的墙. 在他得到锤子i之后，他可以摧毁墙i。
确定他能否达到目标。如果可以，找出他​​行进的最短距离。

样例

输入
3 10
-2 8 -5
5 -10 3
输出
40

解法 一 dp

一共有2 * n + 2个点（原点， x, 2 * n）, 排序，记录位置
dp[i][j][0/1] 表示走过从i 到 j， 当前在i, 或 j 的最小代价
转移从(i, j, 0/1) 到（i - 1, j, 0） 和（i, j + 1, 1) , 再加上距离就行了。
时间O(n² * 4) 空间同理

#include <bits/stdc++.h>
#define fi first 
#define se second
using namespace std;
const int maxn = 4e3 + 10; 
typedef long long ll;
typedef pair<int, int> pii;
int n, x;
int p0, px;
int a[maxn], b[maxn];
pii c[maxn];
ll fL[maxn][maxn], fR[maxn][maxn];
ll ans = 1e18;
int py[maxn], pz[maxn];
signed main() {cin >> n >> x;for (int i = 0; i < n; i++) {cin >> a[i];}vector<pii> v;v.push_back({0, n});v.push_back({x, n + 1}); for (int i = 0; i < n; i++) {cin >> b[i];v.push_back({a[i], i});v.push_back({b[i], ~i});}int sz = (int)v.size();sort(v.begin(), v.end());for (int i = 0; i < v.size(); i++) {if (v[i].se >= 0 && v[i].se < n) py[v[i].se] = i;else if (v[i].se < 0) pz[~v[i].se] = i;if (v[i].se == n + 1) px = i;if (v[i].se == n) p0 = i; }for (int i = 0; i < 4000; i++) for (int j = 0; j < 4000; j++) fL[i][j] = fR[i][j] = 1e18;fL[p0][p0] = 0;fR[p0][p0] = 0;for (int i = p0; i >= 0; i--) {for (int j = p0; j < sz; j++) {if (i <= px && j >= px) {ans = min(ans, fL[i][j]);ans = min(ans, fR[i][j]);}if (i > 0) {int ok = 1;int id = v[i - 1].second;if (id >= 0 && id < n) if (pz[id] < i || pz[id] > j) ok = 0;if (ok) fL[i - 1][j] = min(fL[i - 1][j], fL[i][j] + abs(v[i].fi - v[i - 1].fi)),fL[i - 1][j] = min(fL[i - 1][j], fR[i][j] + abs(v[j].fi - v[i - 1].fi));}if (j < sz - 1) {int ok = 1;int id = v[j + 1].second;if (id >= 0 && id < n) if (pz[id] < i || pz[id] > j) ok = 0;if (ok) fR[i][j + 1] = min(fR[i][j + 1], fL[i][j] + abs(v[i].fi - v[j + 1].fi)),fR[i][j + 1] = min(fR[i][j + 1], fR[i][j] + abs(v[j].fi - v[j + 1].fi));}  }}if (ans < 1e18) cout << ans << endl;else cout << -1 << endl;return 0;
}

解法2 模拟+贪心O(nlogn)7ms

#include <bits/stdc++.h>
#define fi first 
#define se second
using namespace std;
const int maxn = 4e3 + 10; 
typedef long long ll;
typedef pair<int, int> pii;
int n, x;
int a[maxn], b[maxn];
int sl[maxn], sr[maxn];
int l = -1e9, r = 1e9;
signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> x;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < n; i++) cin >> b[i];vector<pii> li, ri;for (int i = 0; i < n; i++) {if (a[i] < 0 && b[i] < 0 || a[i] > 0 && b[i] > 0) {if (abs(a[i]) < abs(b[i])) {if (a[i] > 0) r = min(r, a[i]);else l = max(l, a[i]);}} else {if (a[i] > 0) ri.push_back({a[i], i});else li.push_back({a[i], i});}}sort(li.rbegin(), li.rend());sort(ri.begin(), ri.end());if (l > x || r < x) {cout << -1 << endl;return 0;}int mn = 0, mx = 0;for (auto p:ri) sr[p.se] = min(mn, b[p.se]), mn = min(sr[p.se], mn);for (auto p:li) sl[p.se] = max(mx, b[p.se]), mx = max(sl[p.se], mx);int c = x, nc;ll ans = 0;set<int> mp;while(c != 0) {if (mp.count(c)) {cout << -1 << endl;return 0;}mp.insert(c);if (c > 0) {auto it = lower_bound(ri.begin(), ri.end(), make_pair(c, 0));if (it != ri.begin()) {nc = sr[prev(it)->second];} else nc = 0;} else {auto it = upper_bound(li.rbegin(), li.rend(), make_pair(c, 0));if (it != li.rend()) {nc = sl[it->second];} else nc = 0;}ans += abs(c - nc);c = nc;}cout << ans << endl;return 0;
}