蒟蒻dp15分
查看原帖
蒟蒻dp15分
476720
_pharos_C楼主2023/5/24 13:59

代码如下,想知道方程设的有没有问题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1010;
int n, m, tmp;
int ma[maxn][maxn], dp[maxn][maxn];

signed main() {
	memset(dp, -0x3f3f3f3f, sizeof(dp));
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin >> ma[i][j];
			if(j == 1) {
				tmp += ma[i][j];
				dp[i][1] = tmp;
			}
		}
	}
	for(int j=2; j<=m; j++) {
		dp[1][j] = max(dp[1][j], dp[1][j-1] + ma[1][j]);
		for(int i=2; i<=n; i++) {
			dp[i][j] = max(max(dp[i][j-1] + ma[i][j], dp[i][j]), dp[i-1][j] + ma[i][j]);
		}
		for(int i=n-1; i>=1; i--) {
			dp[i][j] = max(max(dp[i][j-1] + ma[i][j], dp[i][j]), dp[i+1][j] + ma[i][j]);
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}
2023/5/24 13:59
加载中...