蓝桥杯2020年第十一届省赛真题-数字三角形

解题思路:

注意事项:

参考代码:

#include <cstdio>
#include <algorithm>

int n,ans=0;
int a[101][101];
int dp[101][101]={0};

int main(){
	
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			scanf("%d",&a[i][j]);
		}
	}
	dp[0][0]=a[0][0];
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			dp[i][j]=a[i][j]+std::max(dp[i-1][j],dp[i-1][j-1]);
		}	
	}
	if(n%2){
		ans=dp[n-1][n-1>>1];
	}else{
		ans=std::max(dp[n-1][n-1>>1],dp[n-1][(n-1>>1)+1]);
	}
	printf("%d",ans);
	return 0;
}