三维思路 大佬求调啊啊啊!!!
查看原帖
三维思路 大佬求调啊啊啊!!!
421758
HANDSOME_FZZ楼主2023/7/20 08:26
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#define N 52
using namespace std;
int n,m,d[N][N],dp[N*2][N][N];

int main(){
	//freopen("P1006_4.in","w",stdin);
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++) cin>>d[i][j];
	for(int k=1;k<=n+m-3;k++){//已知步数和横坐标是可以求纵坐标的 
		for(int i=1;i<=k+1;i++){
			for(int j=1;j<=k+1;j++){
				//if(k-i+1<0||k-j+1<0||k+2-i>n||k+2-j>n) continue;//纵坐标的合法性 
				if(i==j||i>m||j>m) continue;
				int s=max(dp[k-1][i][j],dp[k-1][i][j-1]);
				int b=max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]);
				dp[k][i][j]=max(s,b)+d[i][k-i+2]+d[j][k-i+2];
				//if (i==j) dp[k][i][j]=0;//判断重合路径???(个人觉得是有问题的)
				//cout<<k<<' '<<i<<' '<<j<<' '<<dp[k][i][j]<<endl;
			}
		}
	}
	cout<<dp[n+m-3][m-1][m];
	return 0;
}
2023/7/20 08:26
加载中...