[JSOI2009] 火星藏宝图

题意

我们从 (1,1) 出发，要走到 (M,M)。

每次只能去右下方向的岛，也就是下一个岛必须满足：

x 不减
y 不减

走到一个岛能拿到这座岛的水果价值，两个岛之间的划船代价是横纵坐标差平方和。

要求最大化：

拿到的水果总价值 - 全部划船代价

思路

先看最直接的暴力 DP：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#include <bits/stdc++.h>
using namespace std;

const long long NEG_INF = -(1LL << 60);
const int MAXN = 200005;

struct Node {
    int x, y;
    long long v;
} a[MAXN];

long long best_value[1005][1005];
long long dp[MAXN];
int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力解。
    // 先把同一格子的价值合并，然后直接在偏序 DAG 上做 O(K^2) DP。
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            best_value[i][j] = -1;
        }
    }

    for (int i = 1; i <= n; i++) {
        int x, y;
        long long v;
        cin >> x >> y >> v;
        best_value[x][y] = max(best_value[x][y], v);
    }

    int cnt = 0;
    for (int x = 1; x <= m; x++) {
        for (int y = 1; y <= m; y++) {
            if (best_value[x][y] >= 0) {
                cnt++;
                a[cnt].x = x;
                a[cnt].y = y;
                a[cnt].v = best_value[x][y];
            }
        }
    }

    for (int i = 1; i <= cnt; i++) {
        dp[i] = NEG_INF;
    }

    for (int i = 1; i <= cnt; i++) {
        if (a[i].x == 1 && a[i].y == 1) {
            dp[i] = a[i].v;
        }
        for (int j = 1; j < i; j++) {
            if (dp[j] <= NEG_INF / 2) {
                continue;
            }
            if (a[j].x <= a[i].x && a[j].y <= a[i].y) {
                long long dx = a[i].x - a[j].x;
                long long dy = a[i].y - a[j].y;
                dp[i] = max(dp[i], dp[j] + a[i].v - dx * dx - dy * dy);
            }
        }
    }

    long long answer = NEG_INF;
    for (int i = 1; i <= cnt; i++) {
        if (a[i].x == m && a[i].y == m) {
            answer = dp[i];
        }
    }

    cout << answer << '\n';
    return 0;
}

设 dp(i) 表示到达岛 i 的最大收益。

如果 j 能转移到 i，那么：

dp(i) = max(dp(j) + v_i - (x_i-x_j)^2 - (y_i-y_j)^2)

把平方项展开：

dp(i) = v_i - x_i^2 - y_i^2 + max(dp(j) - x_j^2 - y_j^2 + 2x_ix_j + 2y_iy_j)

问题在于前驱要同时满足：

x_j <= x_i
y_j <= y_i

这是一个二维偏序约束。

这时利用 M <= 1000 这个条件，可以按列 x 从小到大扫描。

对于历史上的某个点 (x_j, y_j)，如果把 y_j 固定住，那么它对未来列 x 的贡献可以写成一条直线：

f_j(x) = 2x_j * x + (dp(j) - x_j^2 - y_j^2)

所以我们对每一行 y 维护一个凸壳，表示“最后一个点落在这一行”的所有历史状态。

扫描到当前列 x 时：

先对每一行查询出在当前 x 处的最优值 g[y]
再在当前列内部按 y 从小到大处理

当前列内部还要保证前驱的 y_j <= y_i，所以再维护两个凸壳：

prefix_hull：收集所有 y' <= y 的历史行结果
same_column_hull：收集当前列里更上方点的结果

这样就把二维偏序 DP 拆成了两次单调凸包优化。

DP 转移方程

核心状态：

dp(i) 为到达岛 i 的最大收益

核心转移：

dp(i)=v_i-x_i^2-y_i^2+max(dp(j)-x_j^2-y_j^2+2x_ix_j+2y_iy_j)

答案收束：

dp 到终点最大值

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1005;
const long long NEG_INF = -(1LL << 60);

struct Point {
    int y;
    long long v;
    long long dp;
};

struct Line {
    long long k, b;
};

// 按列存点：col[x] 里保存所有横坐标为 x 的岛，按 y 从小到大处理。
vector<Point> col[MAXM];

// best_value[x][y]：同一个格子可能在输入中重复出现，保留价值最大的那个岛即可。
long long best_value[MAXM][MAXM];

int n, m;

// 每一行各维护一个上凸壳，用来做最大值查询。
struct Hull {
    vector<Line> q;
    int head = 0;

    void clear() {
        q.clear();
        head = 0;
    }

    bool empty() const {
        return head >= (int) q.size();
    }

    long long value(const Line &line, long long x) const {
        return line.k * x + line.b;
    }

    // 判断中间那条线是否永远不会成为最优。
    bool bad(const Line &a, const Line &b, const Line &c) const {
        __int128 left = (__int128) (a.b - b.b) * (c.k - b.k);
        __int128 right = (__int128) (b.b - c.b) * (b.k - a.k);
        return left >= right;
    }

    void add_line(long long k, long long b) {
        Line line;
        line.k = k;
        line.b = b;
        while ((int) q.size() - head >= 2 && bad(q[(int) q.size() - 2], q[(int) q.size() - 1], line)) {
            q.pop_back();
        }
        q.push_back(line);
    }

    long long query(long long x) {
        while ((int) q.size() - head >= 2 && value(q[head], x) <= value(q[head + 1], x)) {
            head++;
        }
        return value(q[head], x);
    }
};

Hull row_hull[MAXM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            best_value[i][j] = -1;
        }
        col[i].clear();
        row_hull[i].clear();
    }

    for (int i = 1; i <= n; i++) {
        int x, y;
        long long v;
        cin >> x >> y >> v;
        best_value[x][y] = max(best_value[x][y], v);
    }

    for (int x = 1; x <= m; x++) {
        for (int y = 1; y <= m; y++) {
            if (best_value[x][y] >= 0) {
                Point p;
                p.y = y;
                p.v = best_value[x][y];
                p.dp = NEG_INF;
                col[x].push_back(p);
            }
        }
    }

    long long answer = NEG_INF;

    // g[y]：从之前的列转移到当前列时，最后一个点的纵坐标恰好为 y 的最优值。
    static long long g[MAXM];

    for (int x = 1; x <= m; x++) {
        if (col[x].empty()) {
            continue;
        }

        for (int y = 1; y <= m; y++) {
            g[y] = NEG_INF;
            if (!row_hull[y].empty()) {
                g[y] = row_hull[y].query(x);
            }
        }

        Hull prefix_hull;
        Hull same_column_hull;
        int add_y = 1;

        for (unsigned int i = 0; i < col[x].size(); i++) {
            int y = col[x][i].y;
            long long v = col[x][i].v;

            // 把所有 y' <= y 的历史状态加入前缀凸壳，
            // 对应“前一个点在更左边的列，且纵坐标也不超过当前点”。
            while (add_y <= y) {
                if (g[add_y] > NEG_INF / 2) {
                    prefix_hull.add_line(2LL * add_y, g[add_y]);
                }
                add_y++;
            }

            long long best = NEG_INF;

            if (!prefix_hull.empty()) {
                best = max(best, -1LL * x * x - 1LL * y * y + prefix_hull.query(y));
            }

            // 同一列内还能继续往下走，此时横坐标差是 0，只需要处理纵坐标代价。
            if (!same_column_hull.empty()) {
                best = max(best, -1LL * y * y + same_column_hull.query(y));
            }

            if (x == 1 && y == 1) {
                // 起点必须拿到。
                col[x][i].dp = v;
            } else if (best > NEG_INF / 2) {
                col[x][i].dp = best + v;
            }

            if (col[x][i].dp > NEG_INF / 2) {
                // 给同一列后面的点做转移：
                // dp[j] - (y - yj)^2 = -y^2 + (2*yj)*y + (dp[j] - yj^2)
                same_column_hull.add_line(2LL * y, col[x][i].dp - 1LL * y * y);
            }

            if (x == m && y == m) {
                answer = col[x][i].dp;
            }
        }

        // 当前列处理完后，把这些点作为未来列的候选前驱加入各自行对应的凸壳。
        for (unsigned int i = 0; i < col[x].size(); i++) {
            int y = col[x][i].y;
            long long dp = col[x][i].dp;
            if (dp <= NEG_INF / 2) {
                continue;
            }
            // dp[j] - (x - xj)^2 - (y - yj)^2
            // = -x^2 - y^2 + (2*xj)*x + (2*yj)*y + (dp[j] - xj^2 - yj^2)
            // 对固定 yj 的这一行来说，查询横坐标 x 时就是一条直线。
            row_hull[y].add_line(2LL * x, dp - 1LL * x * x - 1LL * y * y);
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

去重后的岛数记为 K。

时间复杂度 $O(M^2 + K)$ ，空间复杂度 $O(M^2 + K)$ 。

总结

这题的难点不是状态定义，而是怎么利用“只能往右下走”的偏序约束。

把式子展开后，可以看出它本质是：

历史列对当前列的直线查询
当前列内部对纵坐标的前缀最优转移

一旦把这两层拆开，代码结构就清楚了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。