题面

题面

给定一个矩阵，你需要从左上角走到右下角，每一步你可以向右，向上或是向下。你不能重复经过相同的方格，每一个方格上都有一个数，你需要最大化你经过的路径上的数之和。

分析

首先很容易想出较为简易的 $O(n^2m)$ DP 转移方法。

记 $f_{i,j}$ 表示从 $(1,1)$ 走到 $(i,j)$ 的最优答案。

则 $f_{i,j}=\max(f_{k,j-1}+dist_{j,i,k}),1<i\le n$。

其中 $dist_{x,y,z}$ 表示从 $a_{y,x}$ 到 $a_{z,x}$ 直线距离上的所有元素之和。

优化

由于我太菜了，我直接套了一个线段树上去。时间复杂度变为 $O(nmlgn)$，勉强能过这道题。

由于我们更新答案时是按照 $j$ 从小到大更新的，我们考虑 $j-1$ 如何快速推到 $j$。

我们先算出所有的 $f_{k,j-1}+dist_{j,1,k}$，在这个大小为 $n$ 的数组上建线段树。

线段树中你需要维护区间最大值，所以你直接取出根节点的答案就可以更新 $f_{1,j}$ 了，毕竟根节点里面存放的是当前长度为 $n$ 的整个序列中最大的元素，与转移方程相同。

然后我们考虑如何转换得到 $f_{2,j}$，从 $(1,j)$ 走到 $(2,j)$ 过程中，$1$ 号点离你的距离远了 $a_{2,j}$，剩下的点离你的距离近了 $a_{1,j}$，直接在线段树上区间加/减即可。操作完之后取出根节点的答案更新 $f_{2,j}$ 即可。

以此类推，对于 $f_{i,j}$ 转移到 $f_{i+1,j}$，你只需要让线段树上 $[1,i]$ 区间内的所有点加上 $a_{i+1,j}$，让线段树上 $[i+1,n]$ 减去 $a_{i,j}$，然后取出根节点答案直接更新 $f_{i,j}$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;

template <typename T>
T read(void) {
    T f = 1, num = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -f;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        num = (num << 3) + (num << 1) + (c ^ 48);
        c = getchar();
    }
    return f * num;
}

const int maxn = 1005;

long long matrix[maxn][maxn], sum[maxn], f[maxn];

long long tree[maxn << 2], lazy[maxn << 2];
void pushDown(int p) {
    if (!lazy[p]) return;
    tree[p << 1] += lazy[p], tree[p << 1 | 1] += lazy[p];
    lazy[p << 1] += lazy[p], lazy[p << 1 | 1] += lazy[p], lazy[p] = 0;
    return;
}
void build(int p, int l, int r) {  //建树
    if (l == r) return lazy[p] = 0, void(tree[p] = sum[l]);
    pushDown(p);
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    tree[p] = max(tree[p << 1], tree[p << 1 | 1]), lazy[p] = 0;
    return;
}
void add(int p, int l, int r, int ql, int qr, long long delta) {  //区间加
    if (ql <= l && r <= qr) return tree[p] += delta, void(lazy[p] += delta);
    pushDown(p);
    int mid = (l + r) >> 1;
    if (ql <= mid) add(p << 1, l, mid, ql, qr, delta);
    if (qr > mid) add(p << 1 | 1, mid + 1, r, ql, qr, delta);
    tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
    return;
}

int main() {
    int n = read<int>(), m = read<int>();
    for (register int i = 1; i <= n; i++)
        for (register int j = 1; j <= m; j++)
            matrix[i][j] = read<int>();
    for (register int i = 1, s = 0; i <= n; i++) s += matrix[i][1], f[i] = s;
    for (register int j = 2; j <= m; j++) {
        for (register int i = 1, s = 0; i <= n; i++) s += matrix[i][j], sum[i] = f[i] + s;
        build(1, 1, n);  //计算f[1][j]
        f[1] = tree[1];
        for (register int i = 2; i <= n; i++) {  //计算f[i][j]
            add(1, 1, n, 1, i - 1, matrix[i][j]), add(1, 1, n, i, n, -matrix[i - 1][j]);
            f[i] = tree[1];
        }
    }
    printf("%lld\n", f[n]);
    return 0;
}