题解 | 龙与地下城游戏问题

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> a(n, vector<long long>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) cin >> a[i][j];

    const long long INF = (1LL << 60);
    vector<long long> dp(m + 1, INF);   // dp[j]：从 (i,j) 到终点至少需要的血量
    dp[m - 1] = 1;                      // 让右下角用统一转移计算一次

    for (int i = n - 1; i >= 0; --i) {
        dp[m] = INF;                    // 越界哨兵
        for (int j = m - 1; j >= 0; --j) {
            long long need = min(dp[j], dp[j + 1]);
            dp[j] = max(1LL, need - a[i][j]);
        }
    }
    cout << dp[0] << '\n';
    return 0;
}