#include<stdio.h>
#include<string.h>

int n;
short trian[102][102];
short max1[2][102]={0};

int bfs(){
	int maxnum=0;
	int x,y;
	for(int i=1;i<n;++i)
		for(int j=0;j<i;++j)
			for(int k=0;k<2;++k){
				x=i+1;
				y=j+k;
				if(max1[x%2][y]<max1[i%2][j]+trian[x][y])
					max1[x%2][y]=max1[i%2][j]+trian[x][y];
			}
	for(int i=0;i<n;++i)
		if(max1[n%2][i]>maxnum)
			maxnum=max1[n%2][i];
	return maxnum;
}
		
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		for(int j=0;j<i;++j)
			scanf("%d",&trian[i][j]);
	max1[1][0]=trian[1][0];
	printf("%d\n",bfs());
	return 0;
}

• Re:BFS~152K 0MS 水过~~ (673) willdon 2020-11-02 15:51:06