• 欢迎光临~

# 【区间DP】ABC273F. Hammer 2

## ABC273F. Hammer 2

Difficulty:2277、关路灯模型区间DP

### 思路

• 设计 dp 状态：(f[l][r][0/1]) 表示走完区间 [l,r] 最后待在 l(0) 或 r(1) 处的最小移动距离总和，灵感源于P1220 关路灯 。
• dp 转移就很简单了，甚至比关路灯这题还简单，直接看代码就好了，判断一下端点有 wall 时应该怎么转移。
``````vector<int> alls;
vector<PII> v;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int find(int x) {
return lower_bound(ALL(alls), x) - alls.begin() + 1;
}
const int N = 3010;
ll f[N][N][2];

int wall[N], hammer[N], wallpos[N], hammerpos[N];

int main() {
ll n, X;
re(n), re(X);
v.resize(n);
alls.pb(0);
for (int i = 0; i < n; i++) {
re(v[i].first);
alls.pb(v[i].first);
}
for (int i = 0; i < n; i++) {
re(v[i].second);
alls.pb(v[i].second);
}
alls.pb(X);
sort(ALL(alls));
alls.erase(unique(ALL(alls)), alls.end());
for (int i = 0; i < n; i++) {
v[i].first = find(v[i].first);
v[i].se = find(v[i].se);
wall[v[i].first] = i + 1;
hammer[v[i].second] = i + 1;
wallpos[i + 1] = v[i].first;
hammerpos[i + 1] = v[i].second;
}
int tot = SZ(alls);
for (int i = 1; i <= tot; i++) f[i][i][0] = f[i][i][1] = INF;
int start = find(0);
f[start][start][0] = f[start][start][1] = 0;
for (int len = 2; len <= tot; len++) {
for (int l = 1; l + len - 1 <= tot; l++) {
int r = l + len - 1;
f[l][r][0] = INF;
f[l][r][1] = INF;
if (wall[l]) {
int pos = hammerpos[wall[l]];
if (pos >= l + 1 && pos <= r && (f[l + 1][r][0] != INF || f[l + 1][r][1] != INF)) {
f[l][r][0] = min(f[l][r][0], f[l + 1][r][0] + alls[l] - alls[l - 1]);
f[l][r][0] = min(f[l][r][0], f[l + 1][r][1] + alls[r - 1] - alls[l - 1]);
}
}
else {
f[l][r][0] = min(f[l][r][0], f[l + 1][r][0] + alls[l] - alls[l - 1]);
f[l][r][0] = min(f[l][r][0], f[l + 1][r][1] + alls[r - 1] - alls[l - 1]);
}
if (wall[r]) {
int pos = hammerpos[wall[r]];
if (pos >= l && pos <= r - 1 && (f[l][r - 1][0] != INF || f[l][r - 1][1] != INF)) {
f[l][r][1] = min(f[l][r][1], f[l][r - 1][0] + alls[r - 1] - alls[l - 1]);
f[l][r][1] = min(f[l][r][1], f[l][r - 1][1] + alls[r - 1] - alls[r - 2]);
}
}
else {
f[l][r][1] = min(f[l][r][1], f[l][r - 1][0] + alls[r - 1] - alls[l - 1]);
f[l][r][1] = min(f[l][r][1], f[l][r - 1][1] + alls[r - 1] - alls[r - 2]);
}
}
}
ll ans = INF;
int ed = find(X);
for (int i = 1; i <= ed; i++) {
ans = min(ans, f[i][ed][1]);
}
for (int i = ed; i <= tot; i++)
ans = min(ans, f[ed][i][0]);
if (ans == INF) ans = -1;
printf("%lldn", ans);
return 0;
}
``````