posts - 36,  comments - 3,  trackbacks - 0
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少
Input
输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。
Output
对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。
Sample Input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30




#include<stdio.h>
int main()
{
 int C;
 int N;
 scanf("%d",&C);
 while(scanf("%d",&N)&&C!=0)
 {
  int i,j,n;
  int b;
  int a[101][101];
 // int path[109][109];
  int A[101][101];
 
  n=N;
  for(i=0;i<n;i++)
  {
   for(j=0;j<=i;j++)
   {
    scanf("%d",&a[i][j]);
    A[i][j]=a[i][j];
   
   }
  
  }

  for(i=n-1;i>=0;i--)
  {
   for(j=i;j>=0;j--)
   {
    A[i][j]=a[i][j]+A[i+1][j+1];
   // path[i][j]=2;
    if(A[i][j]<=A[i+1][j]+a[i][j])
    {
     A[i][j]=A[i+1][j]+a[i][j];
    // path[i][j]=1;
    }
   }
  }
 
  int max=A[0][0];
  printf("%d",max);
  printf("\n");
  C--;
 }
 return 0;

}



posted on 2012-07-12 16:55 天YU地___PS,代码人生 阅读(166) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航:
 
<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

 一定要好好学习,天天向上!

常用链接

留言簿

随笔分类(8)

随笔档案(35)

文章分类

文章档案(1)

搜索

  •  

最新评论

阅读排行榜

评论排行榜