自动搬运

查看原文

来自洛谷，原作者为

	Tjaweiof 资瓷互关 | 需要壶关请私信 | 蓝名不要再找我互关了 | ENTP-A

搬运于2025-08-24 23:17:43，当前版本为作者最后更新于2025-06-11 15:12:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12722 题解

题目传送门

容易发现，第 $j-2,j-3,\dots$ 列的输出值不可能作为 $(i,j)$ 的输入值。因为其作为 $(i-1,j-1),(i,j-1),(i+1,j)$ 的输入值，并且 $(i-1,j-1),(i,j-1),(i+1,j)$ 的输出值作为 $(i,j)$ 的输入值的时候显然更优。

于是设输出值为 $dp_{i,j}$。

Code

#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout);
int n, m, a[2001][2001], dp[2001][2001], ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	char c;
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> c;
			a[i][j] = c - 48;
		}
	}
	for (int i = 1; i <= m; i++){
		for (int j = 1; j <= n; j++){
			dp[j][i] = max(dp[j - 1][i - 1], max(dp[j][i - 1], dp[j + 1][i - 1])) + a[j][i];
			if (i == m){
				ans = max(ans, dp[j][i] - a[j][i]);
			}
		}
	}
	cout << ans;
	return 0;
}