DP12 龙与地下城游戏问题

思路：dp[i][j]表示到达(i,j)处应该有的最少血量。

我们要求的是初始血量的最小值，那么倒着求，到达(n,m),dp[n][m]=1-a[n][m];

到达dp[i][j]=max(min(dp[i+1][j]-a[i][j],dp[i][j+1]-a[i][j]),1)

描述

给定一个二维数组map，含义是一张地图，例如，如下矩阵

⎩⎨⎧​−2−50​−3−1030​31−5​⎭⎬⎫​

游戏的规则如下:
1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?

根据map,输出初始血量。
 

输入描述：

第一行两个正整数n，m  \left ( 1\leq n,m\leq 10^{3} \right )(1≤n,m≤103)，接下来n行，每行m个整数，代表map_{ij} \left( -10^3 \leq map_{ij} \leq 10^{3}\right )mapij​(−103≤mapij​≤103)。

输出描述：

输出一个整数，表示答案。

示例1

输入：

3 3
-2 -3 3
-5 -10 1
0 30 -5

复制输出：

7

复制

示例2

输入：

2 2
1 1
1 1

复制输出：

1

复制

备注：

时间复杂度O(n*m)O(n∗m),额外空间复杂度O(min(n,m))O(min(n,m))

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int a[1005][1005];
int dp[1005][1005];
int path[1005][1005];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            
        }
    }
    dp[n][m]=max(1-a[n][m],1);
    for(int i=n-1;i>=1;i--)
    {
        dp[i][m]=max(dp[i+1][m]-a[i][m],1);
        
    }
    for(int i=m-1;i>=1;i--)
    {
        dp[n][i]=max(dp[n][i+1]-a[n][i],1);
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=m-1;j>=1;j--)
        {
            dp[i][j]=max(min(dp[i+1][j]-a[i][j],dp[i][j+1]-a[i][j]),1);
        }
    }
    printf("%d\n",dp[1][1]);
    return 0;
}