[Leaf] [P1006] 传纸条

luogu-p1006-传纸条">Luogu-P1006 传纸条

1. 题面梗概

中译中: 给定一个棋盘，棋盘上有权值。要找两条从 $(1,1)$ 到 $(n,m)$ 的路径，要求除了起点和终点，这两条路径不能经过同一个格子。求路径权值和的最大值。

2. 逻辑推导

一去一回，看起来很复杂，同时状态很麻烦，不好处理。

不过我们可以将题目翻译为两个人同时从起点出发去终点。这样我们只需要维护这两个人的位置。

2.1 DP

而既然有两个人，最直观的状态就是两人的位置：

• $f[i][j][k][l]$，表示第一个人走到 $(i,j)$，第二个人走到 $(k, l)$，所获得的最大价值。

由于每个有各有向下向右两种走法，组合起来就有四种状态转移的情况。

• $(i-1,j,k-1,l) \quad (i, j-1,k-1,l) \quad (i-1,j,k,l-1) \quad (i,j-1,k,l-1) \quad$

最后处理 $i == k, j == l$ 的特殊情况即可，因为路径不能重复。

考虑复杂度：$O(N^2M^2)$，虽然在本题问题不大，但是还有优化空间。

2.2 优化

由于两人同时出发，每秒各走一步。在任何时刻 $t$，两人的步数是绝对同步的。

若走过的步数为 $step$（即 $r + c$ ），一旦确定了行坐标 $r$，列坐标 $c$ 也就确定了。

如此，我们就可以使用 $step$ 去替代原本状态的两个列状态。

定义：$f[step][r1][r2]$ 表示：走了 $step$ 步，第一个人在 $r1$ 行，第二个人在 $r2$ 行。

再考虑复杂度：$O((N+M) \cdot N^2)$，这就很优雅了。

不过还是存在那个问题，路径不能重复，如何保证呢？在 DP 循环时，我们强制 $r1 < r2$。这样在任意时刻，二人的坐标都不会重叠。

3. 代码实现

▶

AcCode 朴素版

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

const int maxn = 60;

int a[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];

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

    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 1; j <= m; ++ j )
        {
            for( int k = 1; k <= n; ++ k )
            {
                for( int l = 1; l <= m; ++ l )
                {
                    int mx1 = max( dp[i-1][j][k-1][l], dp[i-1][j][k][l-1] );
                    int mx2 = max( dp[i][j-1][k-1][l], dp[i][j-1][k][l-1] );
                    int mx = max( mx1, mx2 );
                    dp[i][j][k][l] = mx + a[i][j] + a[k][l];
                    if( i == k && j == l )
                    {
                        dp[i][j][k][l] -= a[i][j];
                    }
                }
            }
        }
    }
    
    cout << dp[n][m][n][m];
    return 0;
}

4. 复盘

• 复杂度: 朴素版：$O(N^2M^2)$，优化版：$O( (N+M) \cdot N^2 )$。

• 碎碎念: 这题和 P1004 方格取数很像，不过二者对于重复点的处理不同。

• 关联笔记: 线性DP