1.5.1 Number Triangles 数字金字塔

时间：2014-09-11 23:58:22 收藏：0 阅读：733

★1.5.1 Number Triangles 数字金字塔

一、题目描述

考虑在下面被显示的数字金字塔.
写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大.
每一步可以走到左下方的点也可以到达右下方的点.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30
PROGRAM NAME: numtri
18
INPUT FORMAT
第一个行包含 R(1<= R<=1000) ,表示行的数目.
后面每行为这个数字金字塔特定行包含的整数.
所有的被供应的整数是非负的且不大于100.
SAMPLE INPUT (file numtri.in)
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
OUTPUT FORMAT
单独的一行包含那个可能得到的最大的和.
SAMPLE OUTPUT (file numtri.out)
30

二、解题思路

第一眼见到这个题，我们就要考虑这个题是什么类型？会用到什么算法？一般稍微有点算法基础的就知道，这是一个动态规划问题。

在动态规划问题中，最重要的就是分析你所要关注的状态是什么，然而写出状态转移方程。在状态转移方程中，我们要清楚的明白状态方程的状态表达式是什么含义？是如何从上一状态转移到当前状态的？

对于本题，这是一个简单的动态规划问题（虽然简单，但我还是没想出来，大脑一片混乱。。。）。设f[i,j]表示到达第i层第j个最大的分数。状态转移方程： f[i,j]=Max{f[i+1,j],f[i+1,j+1]}+a[i,j] (1<=i<=n-1,1<=j<=i)我们只需要知道下层的情况，所以可以用滚动数组来记录（降低空间复杂度），时间复杂度O(n^2)，空间复杂度O(n)。（引自http://www.nocow.cn/index.php/USACO/numtri）

下面是我的源代码

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int max(int a,int b){
	return a>b ? a:b;
}
int num[1000][1000],f[1000];

int main(){
	freopen("numtri.in","r",stdin);
	//freopen("numtri.out","w",stdout);

	int R;
	int i,j;
	scanf("%d",&R);
	for (i=0;i<R;i++)
		for(j=0;j<i+1;j++)
			scanf("%d",&num[i][j]);

	for (i=0;i<R;i++)
		f[i]=num[R-1][i];

	for (i=R-1-1;i>=0;i--)
		for (j=0;j<=i;j++)
		{
			f[j]=max(f[j],f[j+1])+num[i][j];}

cout<<f[0]<<endl;

return 0;
}

原文：http://blog.csdn.net/finded/article/details/39213245