题解：P12722 [KOI 2021 Round 2] 计算机器人

Tjaweiof · 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;
}