1163.cpp

北大acm的部分题目答案。绝少水题。均是本人自行求解并通过。

#include<iostream>
using namespace std;
int a[102][102];
//用下三角存储从上面往下的每个点的最大值，每个点只可以到a[i+1][j]和a[i+1][j+1]
int main()
{
	int r,i,j,max;
	cin>>r;
	for(i=0;i<101;i++){a[i][i+1]=a[i][0]=0;}
	for(i=1;i<=r;i++)
	for(j=1;j<=i;j++)
	cin>>a[i][j];
	a[2][1]+=a[1][1];
	a[2][2]+=a[1][1];
	for(i=3;i<=r;i++)
		for(j=1;j<=r;j++)
			if(a[i-1][j]>=a[i-1][j-1])a[i][j]+=a[i-1][j];
			else a[i][j]+=a[i-1][j-1];
	max=a[r][1];
	for(j=2;j<=r;j++)
		if(a[r][j]>max)max=a[r][j];
	cout<<max<<endl;
	return 0;
}