解决思路
如图所示，第 \(j\) 个画家开始画画的时间受限于两个因素
- 自己在上一副图画结束绘画的时间
- 前一个画家在当前图画结束绘画的时间
因此，可以设 \(dp[i][j]\) 为第 \(j\) 个画家在第 \(i\) 幅图画结束绘画的时间，根据以上分析可以得到:
\[dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + t[i][j]
\]
#include <bits/stdc++.h>
int main() {
int m, n; std::cin >> m >> n;
std::vector<std::vector<int>> t(m + 1, std::vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
std::cin >> t[i][j];
}
}
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]) + t[i][j];
}
std::cout << dp[i][n] << " ";
}
std::cout << std::endl;
return 0;
}
更好的解
使用滚动数组降低空间复杂度
#include <bits/stdc++.h>
int main() {
int m, n; std::cin >> m >> n;
std::vector<std::vector<int>> t(m + 1, std::vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
std::cin >> t[i][j];
}
}
std::vector<int> dp(n + 1, 0);
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[j] = std::max(dp[j], dp[j - 1]) + t[i][j];
}
std::cout << dp[n] << " ";
}
std::cout << std::endl;
return 0;
}