3281. 找不到路哒 ultmaster
Time limit per test: 3.0 seconds
Memory limit: 256 megabytes
题意
中华大地上，人人都知道有一个叫做 ultmaster 的 dalao。这倒不是因为他在器乐领域、作曲领域、算法竞赛领域与机器学习领域都已经臻至化境，而是因为他实在是太萌了。
他总是喜欢到世界各处探险，可是呢遗憾的是总有那么些地方不仅难走还危机丛生。
这一次，他来到了一个 m 行 n 列的迷宫，迷宫中有的格子里有可以增加寿元的草药，有的空空如也，有的却有减少寿元的毒气。增加寿元的草药当然要吃，减少寿元的毒气却也不得不吸。在进迷宫之前，ultmaster 拥有的寿元为 h。要保证不能有任何一个时刻寿元值小于 0 （不包括 0），不然 ultmaster 就会死在路上。
迷宫的入口在左上角，出口在右下角，由于 ultmaster 方位感惊人，他竟然能保证自己只往右或者往下走。
那么问题来了，从迷宫出去之后，ultmaster 最多能剩多少寿元呢？
Input
第一行三个整数 $m,n,h (1≤m,n≤1 000,1≤h≤105)$。
接下来的$m$行，每行$n$个整数，分别代表 ultmaster 在相应格子中将要改变的寿元（即这个整数大于 0 为上述的格子内有草药的情况，等于 0 为上述的格子内空空如也的情况，小于 0 为上述的格子内有毒气的情况），每个整数绝对值不超过 100，整数的绝对值表示对寿元产生的影响（即增加或减少的数目）。
output
输出一行一个整数表示答案。
如果 ultmaster 一定会死在路上，输出 −1。
样例
input
2 2 1
0 2
2 -3
output
0
解法：dp
令dp[i][j]表示处于$(i, j)$位置时最大的寿元值，dp转移方向很显然，可以从左侧或上侧转移而来。如果两个方向的值都是负的则将当前值置为-INF。处于要判断出发点是否是负的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 10;
ll a[maxn][maxn];
ll dp[maxn][maxn];
int main(){
int m, n, h;
cin >> m >> n >> h;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
cin >> a[i][j];
dp[0][0] = a[0][0] + h;
if(dp[0][0] < 0)
{
cout << -1 << endl;
return 0;
}
for(int i = 1; i < m; i++)
{
dp[i][0] = dp[i - 1][0] + a[i][0];
if(dp[i][0] < 0)
dp[i][0] = -inf;
}
for(int j = 1; j < n; j++)
{
dp[0][j] = dp[0][j - 1] + a[0][j];
if(dp[0][j] < 0)
dp[0][j] = -inf;
}
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
{
ll t = max(dp[i - 1][j], dp[i][j - 1]);
if(t < 0) {dp[i][j] = -inf;}
else
dp[i][j] = t + a[i][j];
}
cout << max(1LL * -1 ,dp[m - 1][n - 1]) << endl;
return 0;
}