SPOJ AMR11A DP

倒着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;
}