皓宸代码找虫

吴老师

2026-07-30 20:00:02

发布于：广东

3阅读

0回复

0点赞

这份代码的 DP 状态和转移过程基本正确，真正参与编译的代码主要有 两个致命错误。

错误一：`memset(dp,0x3f)` 初始化方向反了

你写的是：

memset(dp,0x3f,sizeof dp);

0x3f 会把每个 long long 初始化成一个很大的正数，约为：

4.557e18

但你的 DP 求的是最大值：

dp[...] = max(dp[...], 新状态);

求最大值时，不可达状态必须初始化成很小的负数，而不能是很大的正数。

否则，例如：

dp[i][j][1][0]

初始就是一个极大值，真实路径算出的价值只有几百万：

max(极大值, 合法路径价值)

结果永远还是极大值。

更严重的是，不可达状态也会继续转移：

dp[i - 1][j][l][1] + a[i][j]

相当于：

极大值 + 当前权值

于是程序会制造出大量根本不存在的“超大价值路径”。

应改成负无穷，例如：

memset(dp,0xcf,sizeof dp);

或者更清楚地写：

const ll NEG = -(1LL << 60);

for(int i = 0; i < 510; i++)
    for(int j = 0; j < 510; j++)
        for(int l = 0; l < 11; l++)
            for(int d = 0; d < 2; d++)
                dp[i][j][l][d] = NEG;

这里的原则是：

求最小值：不可达初始化为正无穷；
求最大值：不可达初始化为负无穷。

错误二：最终答案把两条不同路径加起来了

你写的是：

for(int i=0;i<=k;i++){
    ans=max(ans,dp[n][m][i][1]+dp[n][m][1][0]);
}

这个式子完全不符合 DP 状态的含义。

其中：

dp[n][m][i][1]

表示以“向右”为最后方向、连续走了 $i$ 步的一条路径。

而：

dp[n][m][1][0]

表示以“向下”为最后方向、连续走了 $1$ 步的另一条路径。

这两个值对应的是两条不同的完整路径，不能相加。

题目要求选择一条路径，所以应该在所有终点状态中取最大值：

for(int i = 0; i <= k; i++){
    ans = max(ans, dp[n][m][i][0]);
    ans = max(ans, dp[n][m][i][1]);
}

也可以写成：

for(int i = 0; i <= k; i++){
    ans = max(ans, max(dp[n][m][i][0], dp[n][m][i][1]));
}

此外，你原来的式子还固定使用：

dp[n][m][1][0]

因此只检查了“最后连续向下 $1$ 步”的状态，完全遗漏了：

dp[n][m][2][0]
dp[n][m][3][0]
...
dp[n][m][k][0]

DP 状态定义是正确的

你的状态：

dp[i][j][l][0]

表示到达 $(i,j)$ ，最后连续向下走了 $l$ 步时的最大价值。

dp[i][j][l][1]

表示到达 $(i,j)$ ，最后连续向右走了 $l$ 步时的最大价值。

这个状态设计正确。

起点初始化正确

dp[1][1][0][0]=dp[1][1][0][1]=a[1][1];

起点没有发生移动，所以连续步数是 $0$ 。

同时把两个方向都设为起点价值，是为了方便初始化第一行和第一列，这样写可以。

第一列初始化正确

for(int i=2;i<=min(k+1,n);i++){
    dp[i][1][i-1][0]=dp[i-1][1][i-2][0]+a[i][1];
}

到达 $(i,1)$ 只能连续向下走 $i-1$ 步。

因为最多连续走 $K$ 步，所以只初始化到：

$i-1\le K$

也就是：

$i\le K+1$

这部分正确。

第一行初始化正确

for(int j=2;j<=min(k+1,m);j++){
    dp[1][j][j-1][1]=dp[1][j-1][j-2][1]+a[1][j];
}

到达 $(1,j)$ 只能连续向右走 $j-1$ 步，逻辑同样正确。

四类状态转移都正确

从向右切换为向下

dp[i][j][1][0]
=
max(dp[i][j][1][0],
    dp[i-1][j][l][1]+a[i][j]);

原来最后向右，现在向下，连续向下次数变为 $1$ ，正确。

继续向下

if(l<k)
    dp[i][j][l+1][0]
    =
    max(dp[i][j][l+1][0],
        dp[i-1][j][l][0]+a[i][j]);

连续向下次数从 $l$ 变成 $l+1$ ，并保证不超过 $K$ ，正确。

从向下切换为向右

dp[i][j][1][1]
=
max(dp[i][j][1][1],
    dp[i][j-1][l][0]+a[i][j]);

正确。

继续向右

if(l<k)
    dp[i][j][l+1][1]
    =
    max(dp[i][j][l+1][1],
        dp[i][j-1][l][1]+a[i][j]);

正确。

修正后的关键代码

只需要把两处关键位置改掉：

memset(dp,0xcf,sizeof dp);

最终答案改成：

ll ans = -1;

for(int l = 0; l <= k; l++){
    ans = max(ans, dp[n][m][l][0]);
    ans = max(ans, dp[n][m][l][1]);
}

完整修正版：

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 505;

ll n,m,k;
ll a[1010][1010];
ll dp[510][510][11][2];

int main(){
    freopen("y.in","r",stdin);
    freopen("y.out","w",stdout);

    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    // 最大值 DP，不可达状态应初始化为负无穷
    memset(dp,0xcf,sizeof dp);

    dp[1][1][0][0] = dp[1][1][0][1] = a[1][1];

    // 第一列：只能一直向下
    for(int i = 2; i <= min(k + 1,n); i++){
        dp[i][1][i - 1][0]
            = dp[i - 1][1][i - 2][0] + a[i][1];
    }

    // 第一行：只能一直向右
    for(int j = 2; j <= min(k + 1,m); j++){
        dp[1][j][j - 1][1]
            = dp[1][j - 1][j - 2][1] + a[1][j];
    }

    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            for(int l = 1; l <= k; l++){
                // 由向右切换为向下
                dp[i][j][1][0]
                    = max(dp[i][j][1][0],
                          dp[i - 1][j][l][1] + a[i][j]);

                // 继续向下
                if(l < k){
                    dp[i][j][l + 1][0]
                        = max(dp[i][j][l + 1][0],
                              dp[i - 1][j][l][0] + a[i][j]);
                }

                // 由向下切换为向右
                dp[i][j][1][1]
                    = max(dp[i][j][1][1],
                          dp[i][j - 1][l][0] + a[i][j]);

                // 继续向右
                if(l < k){
                    dp[i][j][l + 1][1]
                        = max(dp[i][j][l + 1][1],
                              dp[i][j - 1][l][1] + a[i][j]);
                }
            }
        }
    }

    ll ans = -1;

    for(int l = 0; l <= k; l++){
        ans = max(ans, dp[n][m][l][0]);
        ans = max(ans, dp[n][m][l][1]);
    }

    cout << ans;

    return 0;
}