本地AC,洛谷RE?
查看原帖
本地AC,洛谷RE?
557975
runner_362楼主2022/12/24 09:36

0pts,求助,为什么会RE?
本jr孤陋寡闻,不懂为什么会RE

算法:两个dp

record

# include <iostream>
# include <math.h>
using namespace std;

int n, m, a[1005][1005];
int dpd[1005][1005], dpu[1005][1005];
// 一个dp_down, 一个dp_up
// dpd存储从右来或者从上来的最大和
// dpu存储从右来或者从下来的最大和

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	}
	
	for (int i = 0; i <= 1005; ++i) {
		for (int j = 0; j <= 1005; ++j) {
			dpd[i][j] = -1e9;
		}
	}
	for (int i = 0; i <= 1005; ++i) {
		for (int j = 0; j <= 1005; ++j) {
			dpu[i][j] = -1e9; 
		}
	}
	dpd[1][0] = 0;

	for (int j = 1; j <= m; ++j) {
		for (int i = 1; i <= n; ++i) {
			dpd[i][j] = max(dpd[i - 1][j], max(dpd[i][j - 1], dpu[i][j - 1])) + a[i][j];
		}
		for (int i = n; i >= 1; --i) {
			dpu[i][j] = max(dpu[i + 1][j], max(dpd[i][j - 1], dpu[i][j - 1])) + a[i][j];
		}
	}

	//cout << endl;
	//for (int i = 1; i <= n; ++i) {
	//	for (int j = 1; j <= m; ++j) {
	//		cout << dpd[i][j] << "," << dpu[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	
	cout << dpd[n][m] << endl;

	return 0;
}
2022/12/24 09:36
加载中...