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

zzd13 · 2026-10-23 16:10:30 · 题解

解题思路

由于机器人只能接收之前列的输出，因此按列进行 DP。

对当前机器人而言，满足条件的来源中，距离较远的列不会比相邻列提供更大的值，因为权重均为正数。因此只需考虑前一列的同行及相邻行。

状态定义和转移

设 f_{i,j} 表示第 j 列第 i 行机器人的存储值，D_{i,j} 表示其权重，初始状态 f_{i,0}=0，转移方程为：

其中，忽略越界的行。

由于转移仅依赖前一列的状态 f_{i-1,j-1}、f_{i,j-1} 和 f_{i+1,j-1}，因此可以用滚动数组优化，将 DP 的额外空间从 O(MN) 降至 O(M)。

时间复杂度为 O(MN)。

代码实现

#include<bits/stdc++.h>
int m,n,i,j,f[2002],g[2002];
char s[2002][2002];
int main(){
    scanf("%d%d",&m,&n);
    for(i=0;i<m;++i)
        scanf("%s",s[i]);
    for(j=1;j<n;++j){
        for(i=0;i<m;++i)
            g[i]=std::max({
                f[i]+s[i][j-1],
                i>0?    f[i-1]+s[i-1][j-1]:0,
                i+1<m?  f[i+1]+s[i+1][j-1]:0
            })-'0';
        std::copy(g,g+m,f);
    }
    printf("%d",*std::max_element(f,f+m));
}