HDU - 2084 - 数塔

2019-11-08 03:07:55

字体：大中小

来源：转载

供稿：网友

HDU - 2084 - 数塔

应该是最简单的DP了吧。

题目

omg

解题过程

正常DP

先把数据读入；再从顶层到底层dp，分行首、行尾和行中三种情况；最后在最后一行总和中循环出最大的数，输出即可。

跟上一个相对应的就应该是“不正常”的DP了吧

和第一个唯一的区别就是从底层到顶层进行dp 最后会直接得到最小值；比较机(zhi)智(zhang)吧，哈哈哈！

Ac代码

正常DP

// 2084 - 数塔int main() { const int maxn = 1005; int C, N; int map[maxn][maxn]; int num; cin >> C; while (C--) { cin >> N; num = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { cin >> map[i][j]; } } // 顺序dp（需单独考虑行首与行尾的情况） for (int i = 2; i <= N; i++) { for (int j = 1; j <= N; j++) { if (j == 1) { map[i][j] += map[i - 1][j]; } else if (j == i) { map[i][j] += map[i - 1][j - 1]; } else { map[i][j] += max(map[i - 1][j - 1], map[i - 1][j]); } } } for (int i = 1; i <= N; i++) { num = max(num, map[N][i]); } cout << num << endl; } return 0;}

“不正常”DP

// 2084 - 数塔int main() { const int maxn = 1005; int C, N; int map[maxn][maxn]; int num[maxn]; cin >> C; while (C--) { cin >> N; for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { cin >> map[i][j]; } } memset(num, 0, sizeof(num)); // 从尾至头dp for (int i = N; i > 0; i--) { for (int j = 1; j <= i; j++) { num[j] = max(num[j], num[j + 1]) + map[i][j]; } } cout << num[1] << endl; } return 0;}