题目大意
从左上角出发，沿向上，向下，向右三个方向移动到达右下角。求所经过方格的数字总和的最大值。
分析
因为小熊不能向左移动，所以去除了小熊向下后再向左移动或向上后再向左的可能，不具有后效性（也就是我们只用考虑向上，向下，向右三个方向），考虑动态规划或记忆化搜索，当然也可以考虑暴力二十分。为了方便，设起始点为 ，终末点为 ，并且设 为点 的方向为 时的最大值，其中 为行， 为列。
我们规定
记忆化搜索做法
从点 出发到达 所能获得的最大值等于从点 出发到达 所能获得的最大值，而到达点 的最大值等于 ，与 ，与 的最大值加上 ，其中 表示 的方向向上时的最大值，其余同理。
需要注意，当在一列中方向已经确定向上，则不可变为向下，但可以变为向右（或向左），因为是从右下角出发走向左上角，所以方向不能向右。
设 ，有
注意边界情况，这里就不展开了。
目标： 。
动态规划做法
俗话说，能用记忆化搜索做的题就能用动态规划，它们实际上可以相互转化。
边界特判
对于第一列的特判。
显然， ， 又可知对于任意 都有 （不能向上），又因为 ， 而此时 （无法向上），所以 。第一列（初始状态或边界）处理完毕。
整理可得 ，因为 数组初始值为 ，所以不需要特判 。
还要注意对第一行与最后一行的特判，在状态转移方程中会提及。
状态转移方程
前提： 。
其实根据记忆化搜索已经可知，将 转化为 即可，但是需注意 ，原因：我们已知 ， 易知 。
边界：当 时， ，当 时， 。
最后输出 。
优化：观察到输入规模为 ，最坏时为 。所以可以采用快读。
附：快读代码。
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
AC代码
记忆化搜索
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[1001][1001], dp[1001][1001][3];
long long dfs(int x, int y, int d) {
if (dp[x][y][d] != INT_MIN) {
return dp[x][y][d];
}
long long maxn = INT_MIN;
if (x != 1 && d != 2) {
maxn = dfs(x - 1, y, 1);
}
if (x != n && d != 1) {
maxn = max(maxn, dfs(x + 1, y, 2));
}
if (y != 1) {
maxn = max(maxn, dfs(x, y - 1, 0));
}
return dp[x][y][d] = max(dp[x][y][d], maxn + a[x][y]);
}
int main() {
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%lld", &a[i][j]);
for (int k = 0; k <= 2; ++k) {
dp[i][j][k] = INT_MIN;
}
}
}
dp[1][1][1] = dp[1][1][0] = a[1][1];
printf("%lld", dfs(n, m, 0));
return 0;
}
动态规划
#include <bits/stdc++.h>
using namespace std;
int n, m, a[1001][1001];
long long dp[1002][1002][3];
int main() {
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &a[i][j]);
}
}
dp[1][1][1] = dp[1][1][2] = dp[1][1][0] = a[1][1];
for (int i = 2; i <= n; ++i) {
dp[i][1][2] = dp[i][1][0] = dp[i - 1][1][2] + a[i][1];
}
for (int j = 2; j <= m; ++j) {
dp[1][j][2] = dp[1][j - 1][0] + a[1][j];
for (int i = 2; i <= n; ++i) {
dp[i][j][2] = max(dp[i - 1][j][2], dp[i][j - 1][0]) + a[i][j];
}
dp[n][j][1] = dp[n][j - 1][0] + a[n][j];
for (int i = n - 1; i >= 1; --i) {
dp[i][j][1] = max(dp[i + 1][j][1], dp[i][j - 1][0]) + a[i][j];
}
for (int i = 1; i <= n; ++i) {
dp[i][j][0] = max(dp[i][j][1], dp[i][j][2]);
}
}
printf("%lld", dp[n][m][0]);
return 0;
}
共 2 条回复
👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍
👍👍👍