题解 | 收集金币 | DAG 上 DP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;

int n, m, q;
int a[N][N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 0; i <= n; i++) a[i][0] = -1e9;
    for(int j = 0; j <= m; j++) a[0][j] = -1e9;
    cin >> q;
    while (q--) {
        int x, y, v;
        cin >> x >> y >> v;
        if (x + y - 2 >= v) {
            a[x][y] = -1e9;
        }
    }
    int ans = a[1][1];
    for (int s = 3; s <= n + m; s++) {
        for (int i = 1; i < s; i++) {
            int j = s - i;
            if(i > n || j > m) continue;
            a[i][j] += max(a[i - 1][j], a[i][j - 1]);
            a[i][j] = max(a[i][j], (int)-1e9);
            ans = max(ans, a[i][j]);
        }
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}
// 64 位输出请用 printf("%lld")