`

poj 3176

 
阅读更多

大致题意:

输入一个n层的三角形,第i层有i个数,求从第1层到第n层的所有路线中,权值之和最大的路线。

规定:第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。

解题方法:

用二维数组way[][]靠左存储三角形内的数据,那么连线规则变更为

way[i][j] → Way[i+1][j]

 Way[i][j] → Way[i+1][j+1]

 

注意:way[][]初始化为输入时的三角形数值,此时way[i][j]表示该点位置上的权值,没输入的位置初始化为0。

 

代码如下:

#include <iostream>
using namespace std;

const int N=360;
int wei[N][N],n;

int max(int a, int b)
{
	return a>b?a:b;
}
int main()
{
	int i,j;
	while (cin>>n)
	{
		for (i=0;i<N;i++)
			for(j=0;j<N;j++)
				wei[i][j]=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=i;j++)
				cin>>wei[i][j];
		}
		int max_weight=0;
		for (i=1;i<=n;i++)
		{
			for(j=1;j<=i;j++)
			{
				wei[i][j]+=max(wei[i-1][j-1],wei[i-1][j]);
				if (i==n&&max_weight<=wei[i][j])
				{
					max_weight=wei[i][j];
				}	
			}
		}
		cout<<max_weight<<endl;
	}
	return 0;
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics