1 条题解
-
0
记忆化搜索
#include <bits/stdc++.h> using namespace std; int r; int a[1005][1005]; // 走到 (x,y) 的最大值 int book[1005][1005]; int f(int x, int y) { if (book[x][y] != -1) return book[x][y]; if (x == 1 && y == 1) return book[x][y] = a[x][y]; if (y == 1) return book[x][y] = f(x - 1, y) + a[x][y]; if (y == x) return book[x][y] = f(x - 1, y - 1) + a[x][y]; return book[x][y] = max(f(x - 1, y), f(x - 1, y - 1)) + a[x][y]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> r; for (int i = 1; i <= r; i++) for (int j = 1; j <= i; j++) { cin >> a[i][j]; book[i][j] = -1; } int ans = 0; for (int j = 1; j <= r; j++) ans = max(ans, f(r, j)); cout << ans; return 0; }
自己找到顺序递推
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, ans; int a[1005][1005]; //dp[i][j] 从(1,1)走到(i,j)位置和的最大值 int dp[1005][1005]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) cin >> a[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) if (i == 1) dp[i][j] = a[i][j]; else if (j == 1) dp[i][j] = dp[i - 1][j] + a[i][j]; else if (j == i) dp[i][j] = dp[i - 1][j - 1] + a[i][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j]; ans = -1; for (int j = 1; j <= n; j++) ans = max(ans, dp[n][j]); cout << ans << endl; return 0; }
- 1
信息
- ID
- 941
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 50
- 已通过
- 28
- 上传者