Number Triangles
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be 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.
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
PROGRAM NAME: numtri
INPUT FORMAT
The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
SAMPLE INPUT (file numtri.in)
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
OUTPUT FORMAT
A single line containing the largest sum using the traversal specified.
SAMPLE OUTPUT (file numtri.out)
30
解题思路:经典的DP问题。状态转移方程:f[i][j]=a[i][j]+max(f[i-1,j-1],f[i-1,j])。把数组开成局部变量了,然后IDE一运行就中断结束了。题解到USACO上居然AC了。然后纠结了好久才找到原因。以后记得大数组开成全局的。
View Code
1 /* 2 ID:spcjv51 3 PROG:numtri 4 LANG:C 5 */ 6 #include<stdio.h> 7 int a[1005][1005],f[1005][1005]; 8 int max(int a,int b) 9 { 10 return(a>b?a:b); 11 } 12 int main(void) 13 { 14 freopen("numtri.in","r",stdin); 15 freopen("numtri.out","w",stdout); 16 int i,j,n,ans; 17 scanf("%d",&n); 18 memset(f,0,sizeof(f)); 19 for(i=1; i<=n; i++) 20 for(j=1; j<=i; j++) 21 scanf("%d",&a[i][j]); 22 f[1][1]=a[1][1]; 23 for(i=2; i<=n; i++) 24 for(j=1; j<=i; j++) 25 f[i][j]=a[i][j]+max(f[i-1][j],f[i-1][j-1]); 26 ans=-1; 27 for(j=1; j<=n; j++) 28 if(f[n][j]>ans) ans=f[n][j]; 29 printf("%d\n",ans); 30 return 0; 31 }