# POJ 1163 The Triangle【dp+杨辉三角加强版(递归)】

## The Triangle

Time Limit: 1000MS

Memory Limit: 10000K

Total Submissions: 49955

Accepted: 30177

Description

```7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(Figure 1)```

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output

Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

```5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5```

Sample Output

`30`

Source

IOI 1994

d[i][j] += d[i+1][j] > d[i+1][j+1] ? d[i+1][j] : d[i+1][j+1];

``` 1 #include <stdio.h>
2 #include <string.h>
3 int max(int a,int b)
4 {
5     return a>b?a:b;
6 }
7 inline int read()
8 {
9     int x=0,f=1;
10     char ch=getchar();
11     while(ch<'0'||ch>'9')
12     {
13         if(ch=='-')
14             f=-1;
15         ch=getchar();
16     }
17     while(ch>='0'&&ch<='9')
18     {
19         x=x*10+ch-'0';
20         ch=getchar();
21     }
22     return x*f;
23 }
24 inline void write(int x)
25 {
26     if(x<0)
27     {
28         putchar('-');
29         x=-x;
30     }
31     if(x>9)
32     {
33         write(x/10);
34     }
35     putchar(x%10+'0');
36 }
37 int a[101][101],d[101][101];
38 int n;
39 int dp(int i,int j)
40 {
41     if(d[i][j]>=0)
42         return d[i][j];
43     return d[i][j]=a[i][j]+(i==n-1?0:max(dp(i+1,j),dp(i+1,j+1)));
44 }
45 int main()
46 {
47     int i,j;
48     while(scanf("%d",&n)!=EOF)
49     {
50         for(int i=0;i<n;i++)
51         for(j=0;j<i+1;j++)
52             scanf("%d",&a[i][j]);
53         memset(d,-1,sizeof(d));
54         printf("%d\n",dp(0,0));
55     }
56   return 0;
57 }```

0 条评论

## 相关文章

### HDUOJ------2398Savings Account

Savings Account Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

32070

16900

### hdu----（2586）How far away ？（DFS/LCA/RMQ）

How far away ？ Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

29280

### POJ 1015 Jury Compromise（双塔DP）

Jury Compromise Time Limit: 1000MS Memory Limit: 65536K Total Submissio...

29440

### poj-----(2528)Mayor's posters(线段树区间更新及区间统计+离散化)

Mayor's posters Time Limit: 1000MS Memory Limit: 65536K Total Submission...

28340

### ZOJ 3332 Strange Country II

Strange Country II ---- Time Limit: 1 Second      Memory Limit: 32768 KB      Sp...

36350

### HDUOJ----专题训练C

Problem C Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (J...

28960

30750

### hdu---1506(Largest Rectangle in a Histogram/dp最大子矩阵)

Largest Rectangle in a Histogram Time Limit: 2000/1000 MS (Java/Others)    Memor...

29450

### poj----Maximum sum(poj 2479)

Maximum sum Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3...

29760