90分玄关求调
查看原帖
90分玄关求调
1062132
Danubius楼主2024/9/5 20:55
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,G[N][N];
int f[N],up[N],down[N];//往上找和往下找 
//每一列如果选择向下走就只能一直向下了。反之就只能向上了 
//这里都是f作用于记录第i列最大值,up和down都只记录于遍历到的这一列 
int main()
{
	memset(G,-0x3f,sizeof(G));
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin >> G[i][j];
		}
	}
	
	f[1]=G[1][1];
	
	for(int i=2;i<=n;i++)//先拿到第一列的所有值 
	{
		f[i]=f[i-1]+G[i][1]; 
	} 
	
	for(int j=2;j<m;j++)
	{
		memset(down,0,sizeof(down));
		memset(up,0,sizeof(up));
		down[1]=f[1]+G[1][j];
		up[n]=f[n]+G[n][j];
		for(int i=2;i<=n;i++)
		{
			down[i]=max(f[i],down[i-1])+G[i][j];//向下拿上一行 
		}
		for(int i=n-1;i>=1;i--)
		{
			up[i]=max(f[i],up[i+1])+G[i][j];//向上拿下一行 
		}
		for(int i=1;i<=n;i++)
		{
			f[i]=max(down[i],up[i]);	
		}
	}
	
	//现在f[i]存储了第m-1列第i行的最大值;
	//现在往后推第m行的值 
	f[1]+=G[1][m];
	for(int i=2;i<=n;i++) 
	{
		f[i]=max(f[i]+G[i][m],f[i-1]+G[i][m]);//选择当前或者切入 
	}
	
	cout << f[n] << endl; 

	return 0;
}
2024/9/5 20:55
加载中...