Input
輸入數據首先包括一個整數C,表示測試實例的個數,每個測試實例的第一行是一個整數N(1 <= N <= 100),表示數塔的高度,接下來用N行數字表示數塔,其中第i行有個i個整數,且所有的整數均在區間[0,99]內。Output
對於每個測試實例,輸出可能得到的最大和,每個實例的輸出占一行。Sample Input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30
題目大意:中文題目。
解題思路:先記錄最後一行的DP值,然後從最後一行開始往上層層遞進。
#include#include #include using namespace std; int a[105][105], d[105][105]; int main() { int n; scanf("%d\n", &n); while (n--) { memset(a, 0, sizeof(a)); memset(d, 0, sizeof(d)); int m; scanf("%d\n", &m); int t = m; int cnt = 1; while (t--) { for (int i = 1; i <= cnt; i++) { scanf("%d", &a[cnt][i]); } cnt++; } for (int i = 1; i <= m; i++) { d[m][i] = a[m][i]; } for (int i = m - 1; i >= 1; i--) { for (int j = 1; j <= i; j++) { d[i][j] = a[i][j] + max(d[i + 1][j], d[i + 1][j + 1]); } } printf("%d\n", d[1][1]); } return 0; }