SP10228题解

本文同步发于洛谷博客，您也可以在题解页面访问。

因为题目输入格式，输出格式和数据范围没给全。所以我补充一下。

题目翻译

输入格式

第一行输入 $T$ 表示有 $T$ 组数据。每组数据中第一行两个整数 $R,C$ ，接下来输入一个 $R$ 行 $C$ 列的网格 $S$ ，如果 $S_{i,j} < 0$ 表示恐龙，否则表示药水。

输出格式

输出包含 $T$ 组数据，每组数据输出一个正整数，表示由单元格 $1,1$ 到单元格 $R,C$ 的最小力量值。

数据范围与约定

$1 \leq T \leq 5$

$2 \leq R,C \leq 500$

$-10^3 \leq S_{i,j} \leq 10^3$

$S_{1,1} = S_{R,C} = 0$

下面回归正轨

---

解题思路

这道题是一道明显的 dp 题。

定义状态：

$dp_{i,j}$ 表示从第 $i$ 行第 $j$ 列走到第 $R$ 行第 $C$ 列所需最小体力值。

初始状态：

$dp_{R,C} = 1$ ，因为 $S_{R,C} = 0$ 且体力值必须为正数，所以最小值是 $1$ 。

最终解：

$dp_{1,1}$ ，从第 $1$ 行第 $1$ 列走到第 $R$ 行第 $C$ 列所需最小体力值。

状态转移：

经过我们前面的分析，我们明白了这是一个逆向 dp。我们从终点往起点推，这一步需要的点数就是下面一步要用的点数的 $\min$ ，加上当前需要的消耗 (减去获得的体力)，且不能小于 $1$ ，因为最少是 $1$ ，小于就 game over 了。

转移方程：

$dp_{i,j}=\left\{ \begin{aligned} \max(1,dp_{i,j+1}-S_{i,j})\ i=R\\ \max(1,dp_{i+1,j}-S_{i,j})\ j=C\\ \max(1,\min(dp_{i+1,j},dp_{i,j+1})-S_{i,j}) \end{aligned} \right.$

核心 Code：

dp[i][j]=1;
for(int i=r;i>0;i--){
			for(int j=c;j>0;j--){
				if(i==r&&j==c){
					continue;
				}
				else if(i==r){
					dp[i][j]=max(1,dp[i][j+1]-a[i][j]);
				}
				else if(j==c){
					dp[i][j]=max(1,dp[i+1][j]-a[i][j]);
				}
				else{
					dp[i][j]=max(1,min(dp[i][j+1],dp[i+1][j])-a[i][j]);
				}
			}
		}