---
title: "传纸条"
created: 2025-11-28
tags:
  - 算法
---

# 传纸条

## 题目 [传纸条](https://www.acwing.com/problem/content/description/277/)

![[image-0fb62fae.png]]

## 思路分析

好题 当赏

再见

怎么可能放弃 (2024.3.5.22:00——2024.3.6.00:30 拿下！）

膜拜铅笔哥%%%

<https://www.acwing.com/solution/content/51293/>

y总视频讲错了

这题思路还是和上一题方格取数一样 都是把x1,y1 x2,y2 转变成n,x1,x2的状态表示

方格取数是从左上角出发两次到右下角 这题是左上角出发一次 右下角出发一次 可以把右下角往左上角走的那个情况调转一下方向 问题转变成上题一样的从左上角出发两次

还有一点不一样的是 之前是可以走重复的点 只不过只取一次的价值 这次变成了一定不能走重复的点 emm 但其实选出来的方案就是不会经过同一个点的
可以完全套用上题的写法

至于为什么最优解法不会经过同一个点（上题可以走重复实际也没走重复）

有以下证明：（看看得了）

**情况一：最优解的两条路线是相互交叉经过的**

![[image-df8f608f.png]]

则我们可以对交叉出来的部分进行路线交换，如下图的操作

![[image-95d59e84.png]]

于是，我们可以发现，所有的交叉路线都会映射成一种一条路线只在下方走，一条路线只在上方走的不交叉路线

因此我们只需集中解决情况二即可

**情况二：最优解的两条路线不交叉，但在某些点有重合**

![[image-80d91c02.png]]

由于方格取数，对于走到相同格子时，只会累加一次格子的价值

于是我们可以使用贪心中的微调法来进行这部分的证明

对于重合的格子，我们必然可以在两条路线中找到额外的一条或两条路线，使得新的路线不发生重合

具体参照下图：

![[image-8e08d6da.png]]

由于原路线是最优解，则必然 wA=wB=0，则最优解路线必然是经过 A或 B的

因此，我们可以通过微调其中的一条路线，使之不经过重合点 C，同时路线的总价值没有减少

得证：最优解路线可以是不经过重复路线的

另外还有证明：

<https://www.acwing.com/solution/content/12389/>

en 反正意思就是这题模型变得和上一题一模一样了 就好像最低通行费和摘花生一样 多了一个可以往上和往左的选择 但是证明后根本不会往左走 只会往右下走
问题变成一模一样的情况

这里就是一个 从左上到右下 走两次 的最大价值的模型

（不能走同一位置或同一位置只能取一次）

证明部分可以不管 知道选出来的答案路径就是不会重复选同一个格子就行了

核心就是 使用f[n][x1][x2]这样的三维状态表示代替f[x1][y1][x2][y2]的四维表示

n表示横纵坐标之和 在走的过程中 同一时刻两条路径的n是相同的

前置问题解决了

就是dp分析了

状态表示 f[k][i][j]

集合：路径长度为k，第一条路线到i,k-i位置，第二条路线到j,k-j位置的所有方案

属性：MAX

![[image-e69843a3.png]]

用v表示当前位置需要累加的价值

当x1≠x2，当前两条路线走到的格子不是同一个，v=w(i,k−i)+w(j,k−j) 当x1=x2，当前两条路线走到了同一个格子中，只需要累加一次
v=w(i,k−i)

                    右右
         下右
   右下               下下

状态计算：f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;

这里有些乱 给一个理顺些的版本

![[image-cf0ebae3.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 55, M = 2 * N;

int n, m;

int w[N][N];

int f[M][N][N];

int main()

{

    cin >> n >> m;

    for (int i = 1; i <= n; ++ i)

    {

        for (int j = 1; j <= m; ++ j)

        {

            cin >> w[i][j];

        }

    }

    for (int k = 2; k <= n + m; ++ k)

    {

        for (int i = 1; i < k && i <= n; ++ i)

        {

            for (int j = 1; j < k && j <= n; ++ j)

            {

                int v = w[i][k - i];

                if (i != j) //判断两条路线是否经过同一个格子 经过的话只需要累加一次

                    v += w[j][k - j];

                f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;

            }

        }

    }

    cout << f[n + m][n][n] << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[简单DP相关模型|简单DP相关模型]] 🏠 [[00-刷题理模型]] ➡️ [[摘花生|摘花生]]