O(nm)DP35分求dalao查错
查看原帖
O(nm)DP35分求dalao查错
252015
Shiroko楼主2020/11/8 10:32
#include<bits/stdc++.h>
using namespace std;

int n, m, a[1005][1005], f[1005][1005][3];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	memset(f, -128, sizeof(f));
	f[0][1][0] = f[0][1][1] = f[0][1][2] = 0;
	f[1][0][0] = f[1][0][1] = f[1][0][2] = 0;
	for (int j = 1; j <= m; j++)
		for (int i = 1; i <= n; i++)
			f[i][j][0] = max(max(f[i - 1][j][1], f[i - 1][j][0]) + a[i][j], f[i][j][0]);
	for (int j = 1; j <= m; j++)
		for (int i = n; i; i--)
			f[i][j][2] = max(max(f[i + 1][j][1], f[i + 1][j][2]) + a[i][j], f[i][j][1]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			f[i][j][1] = max(max(f[i][j - 1][0], max(f[i][j - 1][1], f[i][j - 1][2])) + a[i][j], f[i][j][2]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			f[i][j][0] = max(max(f[i - 1][j][1], f[i - 1][j][0]) + a[i][j], f[i][j][0]);
			f[i][j][1] = max(max(f[i][j - 1][0], max(f[i][j - 1][1], f[i][j - 1][2])) + a[i][j], f[i][j][2]);
			f[i][j][2] = max(max(f[i + 1][j][1], f[i + 1][j][2]) + a[i][j], f[i][j][1]);
		}
	cout << max(f[n][m][0], f[n][m][1]);
}
2020/11/8 10:32
加载中...