P9550 「PHOI-1」晚宴筵题解

FiraCode · 2023-08-16 19:38:00 · 题解

晚宴筵题解：

Subtask 0

由于 w_i \ge i，所以没有负权边。

可以直接模拟题意建边，然后跑一遍 dijkstra。

Subtask 1

由于没有边权限制，可以用 dp。

设 f_{i,j} 表示 (1,1) \sim(i,j) 的最短路。

然后转移就显然是 f_{i,j}=\min_{l1_i \le k \le r1_i,l2_j\le p \le r2_j}\{f_{k, p}+w_i+w_j+w_k+w_p-i-j-k-p\}，然后暴力转移即可。

Subtask 2

可以直接 (1,1) 到，而且没有其他的边了，那么就直接输出 w_i+w_j+w_1+w_1-i-j-2 即可。

当然，第一行第一列除 (1,1) 外都为 inf。

Subtask 3

考虑如何优化 DP。

我们可以把关于 i,j 的放到外面去，也就是 f_{i,j}=\min_{l1_i \le k \le r1_i,l2_j\le p \le r2_j}\{f_{k, p}+w_k+w_p-k-p\}+w_i+w_j-i-j。

然后我们可以发现，对于 \min 中的值，可以用树套树求区间最大值，然后按照 Subtask 1 中的转移方程转移。

然后再把 f_{i,j}+w_i+w_j-i-j 插入树中即可。

#include <bits/stdc++.h>
using namespace std;
/*
省略百行快读
*/

#define min(a,b) (a<b?a:b)

typedef int ll;

const int INF = 0x3f3f3f3f;
const int N = 2010;

ll minV, tr[N << 2][N << 2];
ll a[N << 2][N << 2];
int n;
ll l1[N], r1[N], l2[N], r2[N], w[N];
ll f[N][N];
#define pushupX(deep,rt) tr[deep][rt] = min(tr[deep << 1][rt], tr[deep << 1 | 1][rt])
#define pushupY(deep,rt) tr[deep][rt] = min(tr[deep][rt << 1], tr[deep][rt << 1 | 1])
void buildY(int ly, int ry, int deep, int rt, int flag) {
    if (ly == ry){
        if (flag!=-1)
            tr[deep][rt] = INF;
        else
            pushupX(deep, rt);
        return;
    }
    int m = (ly + ry) >> 1;
    buildY(ly, m, deep, rt << 1, flag);
    buildY(m + 1, ry, deep, rt << 1 | 1, flag);
    pushupY(deep, rt);
}
void buildX(int lx, int rx, int deep) {
    if (lx == rx){
        buildY(1, n + 1, deep, 1, lx);
        return;
    }
    int m = (lx + rx) >> 1;
    buildX(lx, m, deep << 1);
    buildX(m + 1, rx, deep << 1 | 1);
    buildY(1, n + 1, deep, 1, -1);
}
void modifyY(int Y, int val, int ly, int ry, int deep, int rt, int flag) {
    if (ly == ry) {
        if (flag) 
            tr[deep][rt] = val;
        else pushupX(deep, rt);
        return;
    }
    int m = (ly + ry) >> 1;
    if (Y <= m)
        modifyY(Y, val, ly, m, deep, rt << 1, flag);
    else
        modifyY(Y, val, m + 1, ry, deep, rt << 1 | 1, flag);
    pushupY(deep, rt);
}
void modifyX(int X, int Y, int val, int lx, int rx, int deep) {
    if (lx == rx) {
        modifyY(Y, val, 1, n + 1, deep, 1, 1);
        return;
    }
    int m = (lx + rx) >> 1;
    if (X <= m)
        modifyX(X, Y, val, lx, m, deep << 1);
    else
        modifyX(X, Y, val, m + 1, rx, deep << 1 | 1);
    modifyY(Y, val, 1, n + 1, deep, 1, 0);
}
void queryY(int Yl, int Yr, int ly, int ry, int deep, int rt) { 
    if (Yl <= ly && ry <= Yr) {
        minV = min(tr[deep][rt], minV);
        return;
    }
    int m = (ly + ry) >> 1;
    if (Yl <= m)
        queryY(Yl, Yr, ly, m, deep, rt << 1);
    if (m < Yr)
        queryY(Yl, Yr, m + 1, ry, deep, rt << 1 | 1);
}
void queryX(int Xl, int Xr, int Yl, int Yr, int lx, int rx, int rt) {
    if (Xl <= lx && rx <= Xr){
        queryY(Yl, Yr, 1, n + 1, rt, 1);
        return;
    }
    int m = (lx + rx) >> 1;
    if (Xl <= m)
        queryX(Xl, Xr, Yl, Yr, lx, m, rt << 1);
    if (m < Xr)
        queryX(Xl, Xr, Yl, Yr, m + 1, rx, rt << 1 | 1);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> l1[i];
    for (int i = 1; i <= n; ++i) cin >> r1[i];
    for (int i = 1; i <= n; ++i) cin >> l2[i];
    for (int i = 1; i <= n; ++i) cin >> r2[i];
    for (int i = 1; i <= n; ++i) cin >> w[i];

    buildX(1, n + 1, 1);

    for (int i = 0; i <= n + 1; ++i)
        for (int j = 0; j <= n + 1; ++j)
            f[i][j] = 0x3f3f3f3f;
    f[1][1] = 0;
    modifyX(2, 2, w[1] + w[1] - 1 - 1, 1, n + 1, 1);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (i == 1 && j == 1) continue;
            minV = INF;
            queryX(l1[i] + 1, r1[i] + 1, l2[j] + 1, r2[j] + 1, 1, n + 1, 1);
            if (minV != INF) {
                f[i][j] = minV + w[i] + w[j] - i - j;
                modifyX(i + 1, j + 1, f[i][j] + w[i] + w[j] - i - j, 1, n + 1, 1);
            }
        }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (f[i][j] == 0x3f3f3f3f) cout << "inf ";
            else cout << f[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}