Cow Bowling（递归）

 

F - Cow Bowling

  Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u  

Submit Status Practice POJ 3176 

 

Description

 

The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this: 

 

          7 

 

 3   8 

 

 8   1   0 

 

 2   7   4   4 

 

 4   5   2   6   5

Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame. 

 

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable. 

 

Input

 

 

Line 1: A single integer, N 

 

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle. 

 

 

Output

 

 

Line 1: The largest sum achievable using the traversal rules 

 

 

Sample Input

 

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

 

 

Sample Output

 

30

 

 

Hint

 

 

Explanation of the sample: 

 

          7 

         *

 

 3   8 

       *

 

 8   1   0 

       *

 

 2   7   4   4 

       *

 

 4   5   2   6   5

The highest score is achievable by traversing the cows as shown above. 

  题意：

  数N代表一共有多少层，然后从顶层走到最下层，求数加起来的最大和。

  思路：

  这是简单的动态规划题，列出状态转移方程sum[ i ][ j ]=max { sum [ i+1 ][ j ],sum[ i+1 ][ j+1 ] } + a[ i ][ j ]，所以可以从底部开始递推上去，首先先令 sum [N] [1]=a [N] [1]，然后从最底层开始向上循环，循环体为sum[i][j]+=(sum[i+1][j]>sum[i+1][j+1]?sum[i+1][j]:sum[i+1][j+1])+a[i][j],则最后输出sum[1][1]即可算出得数。

  AC：

#include<stdio.h>
int main()
{
	int a[400][400],sum[400][400];
	int N,i,j;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
	  for(j=1;j<=i;j++)
	   scanf("%d",&a[i][j]);
	for(i=1;i<=N;i++)
	  sum[N][i]=a[N][i];
	for(i=N-1;i>=0;i--)
	 for(j=1;j<=N;j++)
	   sum[i][j]+=(sum[i+1][j]>sum[i+1][j+1]?sum[i+1][j]:sum[i+1][j+1])+a[i][j];
	printf("%d\n",sum[1][1]);
}

  总结：

  这是前几天就做过的题，今天再完整的写一遍出来，当做复习一遍。