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;}