传纸条

文章目录

传送门

思路

其实就是求两条路径，我们假设两个人，一起从 ( 1 , 1 ) (1,1) (1,1)开始走，一直走到 ( n , m ) (n,m) (n,m)这点所经过的路径。
我们就定义 f ( p , i , j ) f(p,i,j) f(p,i,j)表示当前走了 p p p步，第一个人走到第 i i i行，第二个人走到第 j j j行的最大好心程度。

我们可以通过 p p p算出两个人的坐标：分别为 ( i , p − i + 1 ) (i,p-i+1) (i,p−i+1)和 ( j , p − j + 1 ) (j,p-j+1) (j,p−j+1)。
那么状态转移方程式为：

f[p][i][j]=max(max(f[p-1][i][j],f[p-1][i-1][j]),max(f[p-1][i][j-1],f[p-1][i-1][j-1]));

由于两条路径经过同一个点的价值只能算一次，所以如果当前 i = = j i==j i==j（相当于两个人的位置重合了），我们只能算一遍该点的价值。
所以我们还要加一句：

f[p][i][j]+=i==j?a[i][p-i+1]:a[i][p-i+1]+a[j][p-j+1];

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,a[55][55],f[55][55][55];

int main() {
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	}
	f[1][1][1]=a[1][1];
	for(int p=2;p<=n+m-1;p++) {//走了p步，走到终点最多n+m-1步 
		for(int i=1;i<=n && i<=p;i++) {//第一个人走到第i行，最多走n行或p行 
			for(int j=1;j<=n && j<=p;j++) {//第二个人走到第i行，最多走n行或p行 
                if(i==1 && j==1) continue;
                f[p][i][j]=max(max(f[p-1][i][j],f[p-1][i-1][j]),max(f[p-1][i][j-1],f[p-1][i-1][j-1]));
                f[p][i][j]+=i==j?a[i][p-i+1]:a[i][p-i+1]+a[j][p-j+1];
            }
		}
	}
	printf("%d",f[n+m-1][n][n]);
	return 0;
} 

切了吗？ N o   w a y No\ way No way.

完美 R E RE RE
我们 f f f数组的第一维是 p p p，所以我们要把 f f f的第一维的大小开到 100 100 100。

A K AK AK代码

#include <bits/stdc++.h>
using namespace std;
int n,m,a[55][55],f[105][55][55];

int main() {
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	}
	f[1][1][1]=a[1][1];
	for(int p=2;p<=n+m-1;p++) {
		for(int i=1;i<=n && i<=p;i++) {
			for(int j=1;j<=n && j<=p;j++) {
                if(i==1 && j==1) continue;
                f[p][i][j]=max(max(f[p-1][i][j],f[p-1][i-1][j]),max(f[p-1][i][j-1],f[p-1][i-1][j-1]));
                f[p][i][j]+=i==j?a[i][p-i+1]:a[i][p-i+1]+a[j][p-j+1];
            }
		}
	}
	printf("%d",f[n+m-1][n][n]);
	return 0;
}