倒着DP,dp[i][j]表示從i,j走到終點的話,i,j點的初始最小體力值
正着DP隻能DP最大得分,是以是錯的,或者可以二分答案,然後正着DP跑看是否合法,因為正着DP在走到每個地方都是以盡量最大體力值的去走,是以符合條件
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
#define ll long long
#define maxn 100005
int R, C;
int grid[505][505];
int dp[505][505];
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &R, &C);
for (int i = 0; i < R; ++i)
{
for (int j = 0; j < C; ++j)
scanf("%d", &grid[i][j]);
}
dp[R - 1][C - 1] = 1;
for (int i = R - 2; i >= 0; --i)
dp[i][C - 1] = max(dp[i + 1][C - 1] - grid[i][C - 1], 1);
for (int i = C - 2; i >= 0; --i)
dp[R - 1][i] = max(dp[R - 1][i + 1] - grid[R - 1][i], 1);
for (int i = R - 2; i >= 0; --i)
{
for (int j = C - 2; j >= 0; --j)
{
dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j]);
}
}
printf("%d\n", dp[0][0]);
}
//system("pause");
//while (1);
return 0;
}