OR75. 走格子游戏
描述
G社正在开发一个新的战棋类游戏，在这个游戏中，角色只能向2个方向移动：右、下。移动需要消耗行动力，游戏地图上划分M*N个格子，当角色移动到某个格子上时，行动力就会加上格子上的值K（-100~100），当行动力<=0时游戏失败，请问要从地图左上角移动到地图右下角至少需要多少起始行动力，注意（玩家初始化到起始的左上角格子时也需要消耗行动力）输入描述
第一行输入格子行列数（格式为 M N），第2~M+1行每行输入N个数，作为格子值K，中间以空格分割；0 < M, N < 1000，-100 < K < 100输出描述
初始最小行动力示例1
输入:
2 3 -2 -3 3 -5 -10 1
输出:
6
C++ 解法, 执行用时: 5ms, 内存消耗: 712KB, 提交时间: 2020-10-31
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#include <stdlib.h>
#include <algorithm>
#include <limits.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define ll long long
using namespace std;
int main() {
int m, n;
scanf("%d%d", &m, &n);
vector<vector<int>> nums(m+1, vector<int>(n+1, 0)), v(m+1, vector<int>(n+1, 0)), dp(m+1, vector<int>(n+1, 1));
for (int i=1; i <= m; i++)
for (int j=1; j <= n; j++)
scanf("%d", &nums[i][j]);
for (int i=1; i <= m; i++)
for (int j=1; j <= n; j++) {
if (i == 1 || j == 1) {
if (i == 1) {
dp[i][j] = max(dp[i][j-1], -(v[i][j-1]+nums[i][j])+1);
v[i][j] = v[i][j-1] + nums[i][j];
} else {
dp[i][j] = max(dp[i-1][j], -(v[i-1][j]+nums[i][j])+1);
v[i][j] = v[i-1][j] + nums[i][j];
}
} else {
dp[i][j] = min(max(dp[i][j-1], -(v[i][j-1]+nums[i][j])+1), max(dp[i-1][j], -(v[i-1][j]+nums[i][j])+1));
v[i][j] = max(v[i][j-1] + nums[i][j], v[i-1][j] + nums[i][j]);
}
//cout << i << " " << j << " " << dp[i][j] << endl;
}
printf("%d\n", dp[m][n]);
return 0;
}
C++ 解法, 执行用时: 5ms, 内存消耗: 732KB, 提交时间: 2020-10-31
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#include <stdlib.h>
#include <algorithm>
#include <limits.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define ll long long
using namespace std;
int main() {
int m, n;
scanf("%d%d", &m, &n);
vector<vector<int>> nums(m+1, vector<int>(n+1, 0)), v(m+1, vector<int>(n+1, 0)), dp(m+1, vector<int>(n+1, 1));
for (int i=1; i <= m; i++)
for (int j=1; j <= n; j++)
scanf("%d", &nums[i][j]);
for (int i=1; i <= m; i++)
for (int j=1; j <= n; j++) {
if (i == 1 || j == 1) {
if (i == 1) {
dp[i][j] = max(dp[i][j-1], -(v[i][j-1]+nums[i][j])+1);
v[i][j] = v[i][j-1] + nums[i][j];
} else {
dp[i][j] = max(dp[i-1][j], -(v[i-1][j]+nums[i][j])+1);
v[i][j] = v[i-1][j] + nums[i][j];
}
} else {
dp[i][j] = min(max(dp[i][j-1], -(v[i][j-1]+nums[i][j])+1), max(dp[i-1][j], -(v[i-1][j]+nums[i][j])+1));
v[i][j] = max(v[i][j-1] + nums[i][j], v[i-1][j] + nums[i][j]);
}
//cout << i << " " << j << " " << dp[i][j] << endl;
}
printf("%d\n", dp[m][n]);
return 0;
}