EOJ3281 找不到路哒 ultmaster

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
#include <bits/stdc++.h>
#define inf 0x7fffffff
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;
}