問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1163思路:
比較基礎、容易的動態規劃
table[i][j]記錄從根節點到第i行第j個元素的最大和
狀態轉移方程:
table[i][j] = max(table[i][j-1], table[i][j]) + num[i][j]
為了節省空間，對于三角形的保存，采用了一維數組
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 101
5 #define MAX_LEN 5051 /* 1+2+3+
+100 */
6 int rows, num[MAX_LEN];
7 int table[MAX_N][MAX_N];
8
9 /* table[i][j] = max(table[i-1][j-1]+num[i][j], table[i-1][j]+num[i][j] */
10 int
11 dp()
12 {
13 int i, j, k, tmp, max, rt;
14 table[0][0] = num[0];
15 for(i=1; i<rows; i++) {
16 tmp = i*(i+1)/2;
17 for(j=0; j<=i; j++) {
18 max = 0;
19 for(k=1; k>=0; k--)
20 if(j-k>=0 && j-k<=i-1) /* parent index: [i-1][j-k] */
21 max = table[i-1][j-k]+num[tmp+j]>max ? table[i-1][j-k]+num[tmp+j] : max;
22 table[i][j] = max;
23 }
24 }
25 rt = 0;
26 for(j=0; j<rows; j++)
27 if(table[rows-1][j] > rt)
28 rt = table[rows-1][j];
29 return rt;
30 }
31
32 int
33 main(int argc, char **argv)
34 {
35 int i, j, tmp;
36 while(scanf("%d", &rows) != EOF) {
37 for(i=0; i<rows; i++) {
38 tmp = i*(i+1)/2;
39 for(j=0; j<=i; j++)
40 scanf("%d", num+(tmp+j));
41 }
42 memset(table, 0, sizeof(table));
43 printf("%d\n", dp());
44 }
45 }