题目描述
给定一个 N*M 的矩阵A,每个格子中有一个整数。
现在需要找到两条从左上角 (1,1) 到右下角 (N,M) 的路径,路径上的每一步只能向右或向下走。
路径经过的格子中的数会被取走,两条路径可以经过同一个格子,但格子中的数 只能被取一次。
求取得的数之和最大是多少。
输入格式
第一行有2个用空格隔开的整数n和m,表示矩阵有n行m列。
接下来的n行是一个n*m的矩阵,每行的m个整数之间用空格隔开。
输出格式
输出一个整数,表示答案。
数据范围
1≤n,m≤50
样例
输入样例:
3 3
0 3 9
2 8 5
5 7 0
输出样例:
34
(洛谷搬运+自己理解)
在同一条斜线(不经过终点的那条)上的点,x+y相等
所以第一重循环k为x+y的值
第二重循环i为左边点的纵坐标
第三重循环为右边点的纵坐标
对于一个点来说,只有4种情况能到达它
所以只要贪最大的情况再加上两个点的好感度即可
C++ 代码
#include<cmath>
#include<stdio.h>
#include<memory.h>
#define M 100 //数组开两倍,因为k为x+y
int a[M][M],F[M][M][M],m,n;
int maxx(int a,int b,int c,int d,int e){return max(a,max(b,max(c,max(d,e))));}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(F,-1,sizeof(F));
F[2][1][1]=0;
for(int k=3;k<m+n;k++) for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++){
int s=maxx(F[k][i][j],F[k-1][i][j],F[k-1][i-1][j],F[k-1][i][j-1],F[k-1][i-1][j-1]);
//F[sum][i][j]=max{F[sum-1][i][j]+F[k-1][i][j-1]+F[k-1][i-1][j]+F[k-1][i-1][j-1]
if(s==-1) continue;
F[k][i][j]=s+a[k-i][i]+a[k-j][j];
}
printf("%d",F[m+n-1][n-1][n]);
//因为i永远比j小,所以答案不在终点,在左边
return 0;
}
三维状态方程,不得了啊,赞!