acWing 275. 传纸条

题意:

给定一个 N*M 的矩阵A,每个格子中有一个整数。

现在需要找到两条从左上角 (1,1) 到右下角 (N,M) 的路径,路径上的每一步只能向右或向下走。

路径经过的格子中的数会被取走,两条路径可以经过同一个格子,但格子中的数 只能被取一次。

求取得的数之和最大是多少。

输入格式

第一行有2个用空格隔开的整数n和m,表示矩阵有n行m列。

接下来的n行是一个n*m的矩阵,每行的m个整数之间用空格隔开。

输出格式

输出一个整数,表示答案。

数据范围

1n,m501≤n,m≤50

输入样例:

3 3
0 3 9
2 8 5
5 7 0

输出样例:

34
题解:

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

状态表示: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);
其中如果两人在相同格子,则 score(k, i, j) 等于这个格子的分值;否则等于两个格子的分值之和。

时间复杂度
一共有 O(n3)O(n3) 个状态,每个状态需要 O(1)O(1) 的计算量,因此总时间复杂度是 O(n3)O(n3)。

代码:

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int f[120][60][60];
int n,m;
int w[60][60];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      scanf("%d",&w[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=w[i][k-i];
                if(i!=j)t+=w[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;
}

 

acWing 275. 传纸条

上一篇:WebApi返回类型设置为json的三种方法


下一篇:[ASP.NET Core 3框架揭秘] 跨平台开发体验: Windows [上篇]