wrong

Lee  •  2个月前


include

using namespace std; int dp[1001][1001]; int a[1001][1001]; int sum[1001][1001];

int main() {

int n, m;
cin >> n >> m;

for (int i = 1; i <= n; i++) {

	for (int j = 1; j <= m; j++) {

		cin >> a[i][j];
		sum[i][j] = sum[i - 1][j] + a[i][j];
	}
}

for (int i = 1; i <= n; i++) {

	dp[i][1] = a[i][1];
}

for (int j = 1; j <= m; j++) {

	dp[1][j] = a[1][j];
}

bool d = false;

for (int j = 2; j <= m; j++) {

	for (int i = 2; i <= n; i++) {

		int ans = 0xf0;

		for (int k = i + 1; k <= n; k++) {

			ans = max(ans, dp[k][j - 1] + sum[k][j] - sum[i][j]);
		}

		if (!d) {
			dp[i][j] = max(dp[i][j - 1], max(ans, dp[i - 1][j])) + a[i][j];

		} else {
			dp[i][j] = max(dp[i][j - 1], max(ans, dp[i - 1][j] - a[i - 1][j] - a[i][j])) + a[i][j];

			if (dp[i][j] == dp[i][j - 1] + a[i][j] || dp[i][j] == dp[i - 1][j] - a[i - 1][j]) {
				d = false;
			} else {
				d = true;
			}
		}
	}

	d = false;
}

for (int i = 1; i <= n; i++) {

	for (int j = 1; j <= m; j++) {

		cout << dp[i][j] << " ";
	}

	cout << endl;
}

return 0;

}


评论:

请先登录,才能进行评论