75分蒟蒻dp求助
查看原帖
75分蒟蒻dp求助
389540
imfkwk楼主2021/5/25 16:47
#include <bits/stdc++.h>
#define int long long
using namespace std;

inline void read(int& x)
{
	x = 0;
	int f = 1;

	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == 45) f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}

	x = x * f;
}

int n, m;
int vl[1001][1001];

int f[1001][1001][3];
/*
0 from left
1 from down
2 from up

f[i][j][0] = max(f[i][j - 1][0], f[i][j - 1][1], f[i][j - 1][2]) + vl[i][j]
f[i][j][1] = max(f[i + 1][j][0], f[i + 1][j][1]) + vl[i][j]
f[i][j][2] = max(f[i - 1][j][0], f[i - 1][j][2]) + vl[i][j]
*/

signed main(void)
{
	read(n); read(m);
	
	for (register int i = 1; i <= n; ++i)
		for (register int j = 1; j <= m; ++j)
			read(vl[i][j]);
	
	for (register int i = 1; i <= n; ++i)
		f[i][0][0] = f[i][0][1] = f[i][0][2] = -2147483647000;
	
	for (register int j = 1; j <= m; ++j)
		f[0][j][0] = f[0][j][1] = f[0][j][2] = -2147483647000;
		
	for (register int j = 1; j <= m; ++j)
		f[n + 1][j][0] = f[n + 1][j][1] = f[n + 1][j][2] = -2147483647000;
	
	f[1][0][2] = 0;
	f[0][1][0] = 0;
	
	for (register int j = 1; j <= m; ++j)
	{
		for (register int i = 1; i <= n; ++i)
			f[i][j][0] = max(f[i][j - 1][0], max(f[i][j - 1][1], f[i][j - 1][2])) + vl[i][j];
		
		for (register int i = n; i >= 1; --i)
			f[i][j][1] = max(f[i + 1][j][0], f[i + 1][j][1]) + vl[i][j];
			
		for (register int i = 1; i <= n; ++i)
			f[i][j][2] = max(f[i - 1][j][0], f[i - 1][j][2]) + vl[i][j];
	}
	
	printf("%lld", max(f[n][m][0], max(f[n][m][2], f[n][m][1])));
	
	return 0;
}

2021/5/25 16:47
加载中...