简单DP,自底向上求最优。
#include <iostream> #include <string> #include <cstdio> using namespace std; int max(int a, int b) { return a > b ? a : b; } int main() { int n; cin >> n ; int data[n][n]; for (int i = 0; i < n; i ++) { for (int j = 0; j <= i; j ++) { cin >> data[i][j]; } } int res[n]; for (int i = 0; i < n; i ++) { res[i] = data[n-1][i]; } for (int i = n-2; i >=0; i --) { for (int j = 0; j <= i; j ++) { res[j] = max(res[j], res[j + 1]) + data[i][j]; } } cout << res[0] << endl; return 0; } /** 5 8 3 8 8 1 0 4 7 5 4 3 5 2 6 5 */
太久没做题了,看了别人的Java代码才明白,没交上去……
全部评论
(0) 回帖