AcWing 275. 传纸条    原题链接    简单

作者： 作者的头像   yxc ,  2019-08-18 23:02:48 ,  所有人可见 ,  阅读 12432

125


19

算法

(线性DP) $O(n^3)$

首先考虑路径有交集该如何处理。
可以发现交集中的格子一定在每条路径的相同步数处。因此可以让两个人同时从起点出发，每次同时走一步，这样路径中相交的格子一定在同一步内。

状态表示：f[k, i, j] 表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。

状态计算：按照最后一步两个人的走法分成四种情况：

  • 两个人同时向右走，最大分值是 f[k - 1, i, j] + score(k, i, j)；
  • 第一个人向右走，第二个人向下走，最大分值是 f[k - 1, i, j - 1] + score(k, i, j)；
  • 第一个人向下走，第二个人向右走，最大分值是 f[k - 1, i - 1, j] + score(k, i, j)；
  • 两个人同时向下走，最大分值是 f[k - 1, i - 1, j - 1] + score(k, i, j)；

注意两个人不能走到相同格子，即i和j不能相等。

时间复杂度

一共有 $O(n^3)$ 个状态，每个状态需要 $O(1)$ 的计算量，因此总时间复杂度是 $O(n^3)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n, m;
int g[N][N];
int f[N * 2][N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &g[i][j]);

    for (int k = 2; k <= n + m; k ++ )
        for (int i = max(1, k - m); i <= n && i < k; i ++ )
            for (int j = max(1, k - m); j <= n && j < k; j ++ )
                for (int a = 0; a <= 1; a ++ )
                    for (int b = 0; b <= 1; b ++ )
                    {
                        int t = g[i][k - i];
                        if (i != j || k == 2 || k == n + m)
                        {
                            t += g[j][k - j];
                            f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                        }
                    }

    printf("%d\n", f[n + m][n][n]);

    return 0;
}

52 评论

用户头像
zeng9999jian   2023-11-20 20:41      5    踩      回复 
#include<bits/stdc++.h>
using namespace std;

const int N = 110;//n+m
int f[N][N][N];
int w[N][N];

int main()
{
    int n,m;
    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 i1=1;i1<=n;i1++)
            for(int i2=1;i2<=n;i2++)
            {
                int j1=k-i1,j2=k-i2;

                if(j1>=1&&j1<=m&&j2>=1&&j2<=m&&i1!=i2)
                {
                    int &x=f[k][i1][i2],t=w[i1][j1]+w[i2][j2];

                    x=max(x,f[k-1][i1-1][i2-1]+t);//下下
                    x=max(x,f[k-1][i1][i2-1]+t);//右下
                    x=max(x,f[k-1][i1-1][i2]+t);//下右
                    x=max(x,f[k-1][i1][i2]+t);//右右
                }
            }
    //(n-1,m) (n,m-1)
    cout<<f[m+n-1][n][n-1];
}
用户头像
pangyou3s   8个月前         踩      回复

为啥是f[m+n-1][n][n-1]而不是f[n+m][n][n]

用户头像
蓝小闲   7个月前    回复了 pangyou3s 的评论      1    踩      回复

因为 i1 不等于 i2 所以无法给 f [n+m][n][n] 赋值，由于w[n][n]==0,所以f[m+n-1][n][n-1]也可以

用户头像
acwing_00852   4个月前    回复了 pangyou3s 的评论         踩      回复

楼主是按照 方格取数 的方法做的，可以证明最优解的两条路径一定不相交（关于为什么不相交看题解第一篇大佬的证明），但我们一定要让它们从（1，1）开始到（n,m)终止，必然可以推出这两条线一定为这样的形式：
第一条线为：（1，2）->..... -> (n-1,m)
第二条线为：（2，1）->..... -> (n,m-1)
所以Dp的最后一步一定是加上w[n-1,m] 和 w[n,m-1]，即为一条路径共走 （n+m-1）- 2 步 ，走到坐标为（n,m-1）或（n-1,m) ，最后输出Dp最后一步的结果

用户头像
acwing_00852   4个月前    回复了 pangyou3s 的评论         踩      回复

输出改为cout<<f[m+n-1][n-1][n]结果也是一样，都是正确的

用户头像
zeng9999jian   2个月前         踩      回复 
#include<bits/stdc++.h>
using namespace std;

const int N = 55;
int f[2 * N][N][N];
// 蓝书里的状态表示确实太麻烦, 状态的第一维不用表示路径长度而是表示横纵坐标之和
/*
于是 f[i][x1][x2] 表示当第一条路径的横坐标x1,第二条路经的横坐标x2, 两条路径横纵坐标之和i时,
路径权值的最大值.
*/
int w[N][N];
int n, m;

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 i = 2; i <= n + m; i++)
        for(int x1 = 1; x1 <= min(i - 1, n); x1++)
            for(int x2 = 1; x2 <= min(i - 1, n); x2++)
            {
                if(x1 == x2) continue; 
                int &p = f[i][x1][x2], W = w[x1][i - x1] + w[x2][i - x2];

                // 四种转移方式:
                p = max(p, f[i - 1][x1  - 1][x2 - 1] + W); //下下
                p = max(p, f[i - 1][x1][x2] + W); // 右右
                p = max(p, f[i - 1][x1 - 1][x2] + W); // 下右 有可能不合法,但不会被更新
                p = max(p, f[i - 1][x1][x2 - 1] + W); //右下 有可能不合法,但不会被更新
            }

    cout << f[n + m - 1][n][n - 1];
    return 0;
}
用户头像
我就是废物   2023-02-06 21:27      5    踩      回复

$o(n^2)$

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 55;
int a[N][N],f[N<<1][N<<1];  //注意这里

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    for(int k=2;k<=m+n;k++) {
        for(int i1=k-1;i1>=1;i1--) {  //注意这里
            for(int i2=k-1;i2>=1;i2--) {
                int j1 = k - i1, j2 = k - i2;
                int t = a[i1][j1];
                if(i1!=i2) t += a[i2][j2];
                f[i1][i2] = t + max({f[i1-1][i2-1],f[i1-1][i2],f[i1][i2],f[i1][i2-1]});

            }
        }
    }
    printf("%d",f[n][n]);
    return 0;
}
用户头像
我就是废物   2023-02-07 00:12         踩      回复

也可以这样

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 55;
int a[N][N],f[N][N];  

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    for(int k=2;k<=m+n;k++) {
        for(int i1=min(k-1,n);i1>=max(1,k-m);i1--) {  //注意这里
            for(int i2=min(k-1,n);i2>=max(1,k-m);i2--) {
                int j1 = k - i1, j2 = k - i2;
                int t = a[i1][j1];
                if(i1!=i2) t += a[i2][j2];
                f[i1][i2] = t + max({f[i1-1][i2-1],f[i1-1][i2],f[i1][i2],f[i1][i2-1]});

            }
        }
    }
    printf("%d",f[n][n]);
    return 0;
}
用户头像
codingwen   2023-05-15 19:35    回复了 我就是废物 的评论         踩      回复

nb

用户头像
咸鱼翻身成牛马   8个月前         踩      回复

为什么在定义那里交换一下数组 a 和 f ，就是错的

用户头像
cgtlth   3个月前      2    踩      回复 
#include<iostream>
using namespace std;

const int N(55);
int g[N][N];
int f[N*2][N][N];

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

    for(int k=2;k<=n+m;k++)
        for(int i1=1;i1<=n;i1++)
            for(int i2=1;i2<=n;i2++)
            {
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j2>=1&&j1<=m&&j2<=m&&(i1!=i2||k==n+m))
                {
                    int& x=f[k][i1][i2];
                    x=max(x,f[k-1][i1-1][i2-1]);
                    x=max(x,f[k-1][i1-1][i2]);
                    x=max(x,f[k-1][i1][i2]);
                    x=max(x,f[k-1][i1][i2-1]);
                    x+=g[i1][j1]+g[i2][j2];
                }
            }
    cout<<f[n+m][n][n]<<endl;

    return 0;
}
用户头像
zhan666nb   2022-12-01 18:47      2    踩      回复

现在方格取数的代码过不了

用户头像
夜语声烦   2023-01-20 22:35      1    踩      回复

完全可以啊，自己写错了而已

用户头像
Tim0509   2023-03-28 10:29         踩      回复

还要考虑边界问题

用户头像
听凭风引_   8个月前      1    踩      回复

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

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

（首先这题也是走两次 一次左上到右下 一次右下到左上 可以把右下到左上的翻转成左上到右下 问题就变成了一样的左上到右下走两次 其次 不能走同一位置或同一位置只能取一次 在证明后 发现选出来的方案其实压根不会走到同一个位置 所以可以把这个强制不能同一位置和同一位置只能取一次值当成一样的情况处理）

证明部分可以先不管（不影响做题 后续懂了思路再回过去看那些证明 抠细节） 知道选出来的答案路径就是不会重复选同一个格子就行了（大佬轻喷）

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

n表示横纵坐标之和 在走的过程中 同一时刻两条路径的n是相同的
（其实用[x1][y1][x2][y2]也是可以写的 只不过维度太多 时间复杂度就很高 这里有一个经验的方法帮我们减少一维还能正常表示这些情况 这次不会下次就会了）

前置问题解决了

然后就是dp分析了

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

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

属性：MAX

用v表示当前位置需要累加的价值
当x1=x2，当前两条路线走到了同一个格子中，只需要累加一次 v=w(i,k−i)
当x1≠x2，当前两条路线走到的格子不是同一个，就需要累加俩次的了 v=w(i,k−i)+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;

#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;
}

ps:不够严谨 但方便听懵的同学理一下思路 （菜的瑟瑟发抖）

用户头像
kkirino   2023-03-04 15:16      1    踩      回复

y总问一下，这题要是想要保存这两条路径该怎么办？

用户头像
Henter   3个月前         踩      回复

为什么初始化成 -0x3f不行？一定要初始化成0？

用户头像
apol1o   2022-03-28 20:10         踩      回复

k == 2 是为什么啊？

用户头像
kimmmm   2022-04-26 13:07         踩      回复

点（1，1）

用户头像
jiayou123   2021-09-17 11:47         踩      回复

include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 60;
int n,m;
int f[N*2][N][N];
int a[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i)
for(int j=1;j<=m;j)
scanf(“%d”,&a[i][j]);

for(int k=2;k<=n+m;k)
for(int i1=1;i1<=n;i1)
for(int i2=1;i2<=n;i2++)
{
int j1=k-i1,j2=k-i2;
if(j1>=1&&j1<=m&&j2>=1&&j2<=m&&i1!=i2)
{
int t=a[i1][j1]+a[i2][j2];
int &x=f[k][i1][i2];
x=max(x,f[k-1][i1][i2]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2-1]+t);
}

    }

//   for(int k=2;k<=n+m;k++)
//      {for(int i1=1;i1<=n;i1++)
//       for(int i2=1;i2<=n;i2++)
//              cout<<f[k][i1][i2]<<' ';
//              cout<<endl;            }

cout<<f[n+m-1][n-1][n];//谁能告诉我为什么这样是对的，而不是f[n+m][n][n]?

return 0;
}

作者：王大行
链接：https://www.acwing.com/solution/content/67306/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

用户头像
改革春风吹满地   2022-01-20 14:59         踩      回复

我觉得是数据弱了

用户头像
小笨   2023-02-03 15:28      1    踩      回复

两条路径分别走了n+m-1步，只差一步到w[n][m]这个点，因为w[n][m]的值为0，所以对最后的结果不影响。这是我的理解

用户头像
div   2020-10-25 21:11         踩      回复

y总，这个和上一个题方格取数感觉完全一样耶

用户头像
rhyyy   2020-09-01 20:35         踩      回复

y总，m,n是否搞反了？

用户头像
yxc   2020-10-10 10:20         踩      回复

没有。我习惯用n表示行数，用m表示列数，和题目描述有所区别。

用户头像
cdd_1   2020-05-02 22:54         踩      回复

闫老师，这个题和方格取数题一样的代码都能过，不允许走同一个点是怎么体现出来的

用户头像
yxc   2020-05-13 22:22         踩      回复

除了起点和终点之外，只有i != j时，才能去更新其它状态，这样就保证了不走同一个格子。

用户头像
yxc   2020-05-13 22:23      1    踩      回复

方格取数那题的代码目前没找到能卡掉的数据。

用户头像
Stella-W   2020-06-19 15:28    回复了 yxc 的评论         踩      回复

233

用户头像
秦淮岸灯火阑珊   2020-09-08 16:19    回复了 yxc 的评论         踩      回复

有位小哥已经证明了，方格取数和本题本质相同

用户头像
yxc   2020-10-13 10:22    回复了 秦淮岸灯火阑珊 的评论         踩      回复

有链接吗

用户头像
小明同学hh   2020-10-13 22:22    回复了 yxc 的评论      1    踩      回复

https://www.acwing.com/solution/content/12389/
有位小哥已经证明了，方格取数和本题本质相同

用户头像
yxc   2020-10-15 13:51    回复了 小明同学hh 的评论      2    踩      回复

棒

用户头像
lwz159   2020-04-04 21:18         踩      回复

i和j为什么从max(1，k-m)开始啊

用户头像
yxc   2020-04-04 22:44      1    踩      回复

因为k - i和k - j要在1到m的范围内。

用户头像
lwz159   2020-04-04 22:54    回复了 yxc 的评论         踩      回复

为啥我把i和j改成从1开始能ac啊

用户头像
yxc   2020-04-04 22:55    回复了 lwz159 的评论         踩      回复

如果超出范围的话状态会是0，在本题中没啥影响。

用户头像
lwz159   2020-04-04 23:15    回复了 yxc 的评论         踩      回复

嗯，谢谢y总

用户头像
小张同学   2020-03-18 09:22         踩      回复

闫老师，请问这题和方格取数 那道题的区别，就只有，这个题不允许走同一个点吗?我觉得和方格取数 那道题一样啊hhh（恕我新手比较愚蠢）

用户头像
yxc   2020-03-25 03:12         踩      回复

对滴，就只有这一个区别。

用户头像
高振羽   2020-03-13 11:54         踩      回复

y总y总，对于重合的格子，第二个人应当是不能走到的，那对于这个点，不应当标记为负无穷吗？

用户头像
yxc   2020-03-14 01:27         踩      回复

不用，因为这个格子以后不会再被用到了，在上述算法中每个格子只会被遍历一次。

用户头像
高振羽   2020-03-14 11:15    回复了 yxc 的评论         踩      回复

谢谢大佬

用户头像
代码有毒   2020-02-28 23:02         踩      回复

五个for循环里面，为什么
if (i != j || i == 1 && i == n )就不行了呢，都是去排除起点和终点，判断是否两个坐标重叠

用户头像
代码有毒   2020-02-28 23:02         踩      回复

其他的都一样，就if判断改了一下

用户头像
yxc   2020-03-03 06:11         踩      回复

再给你次机会，仔细看看这个条件的后半部分，在n > 1的情况下可能成立不。

用户头像
yxc   2020-03-03 06:12         踩      回复

另外i ==1不一定表示在起点，因为j可以取其他的值。

用户头像
代码有毒   2020-03-03 10:46    回复了 yxc 的评论         踩      回复

哦，我明白了，谢谢大佬

用户头像
代码有毒   2020-02-28 22:59         踩      回复

空间复杂度可以降低到二维，不用记录步数，就像多重背包问题

用户头像
yxc   2020-03-03 06:09      1    踩      回复

代码形式上可能一样，但原理区别很大。

用户头像
小树苗   2019-11-14 20:55         踩      回复

题目中不是要求不能走同一个点吗？
所以f[sum][i][i]的情况不是不应该成立吗？

用户头像
yxc   2019-11-19 11:18         踩      回复

我发现之前一直看错题目了，看成每个点可以走两次，但只会被累加一次。现已更正～

用户头像
小树苗   2019-11-26 18:56    回复了 yxc 的评论         踩      回复

谢谢大佬