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

与dp11相比，计算到达终点的最大值的同时，还需要记录路径上的最小值。

#include <iostream>

using namespace std;

int n, m;
int dp[1005][1005];    //骑士到达[i,j]时的最大血量
int ans[1005][1005];    //骑士到达[i,j]时路径上的最低血量

int main(){
    int val;
    
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> val;
            if(i == 0 && j == 0)
                ans[i][j] = dp[i][j] = val;
            else if(i == 0){
                dp[i][j] = dp[i][j-1] + val;
                ans[i][j] = min(ans[i][j-1], dp[i][j]);
            }
            else if(j == 0){
                dp[i][j] = dp[i-1][j] + val;
                ans[i][j] = min(ans[i-1][j], dp[i][j]);
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + val;
                if(dp[i][j] == dp[i-1][j]+val)
                    ans[i][j] = min(ans[i-1][j], dp[i][j]);
                else ans[i][j] = min(ans[i][j-1], dp[i][j]);
            }
        }
    }
    if(n == 1 || m == 1)//只有一条路径
        cout << max(0, -ans[n-1][m-1])+1;//血量最低为1
    else{//到达最后一点时，只能由[n-1][m]或[n][m-1]到达
        //选择两条路径中最大的最少血量，与到达终点时的血量中选出最小值
      	//与计算dp正好相反
        int res = max(ans[n-2][m-1], ans[n-1][m-2]);
        if(res == ans[n-2][m-1])
            res = min(dp[n-2][m-1]+val, res);
        else res = min(dp[n-1][m-2]+val, res);
        cout << max(0, -res)+1;
    }
    
    
    return 0;
}