【区间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("%lld\n", ans);
    return 0;
}