The Triangle
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 49955 | Accepted: 30177 |
Description
7Figure 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.
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
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
题目要求：
输入一个n层的三角形，第i层有i个数，求从第1层到第n层的所有路线中，权值之和最大的路线。
规定：第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。
题目分析：
典型的动态规划。
因此我们可以从下往上推，相邻的两个数中找较大的与上层相加，得出的结果相邻的两个数中再找较大的与上层相加，以此类推。用二维数组d_[][]记录从下到该点的最大值。
核心代码
d[i][j] += d[i+1][j] > d[i+1][j+1] ? d[i+1][j] : d[i+1][j+1];
最后的结果就是d[0][0]。
下面给出AC代码:
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 }
