拿金币 蓝桥杯ALGO1006 有一个N x N的方格,问如何走才能拿到最多的金币

时间:2024-03-07 15:34:13

问题描述

有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

输入格式

第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。

输出格式

最多能拿金币数量。

解题思路

因为要求最多能拿多少金币,所以就想到了贪心,每次都从右边或下边选最大的那个,但这样并不合理,可能会错过最佳选择;还有就是联想到了AOE网,能不能倒着从终点往回找。最后的思路来自知乎用户 一棵小树,对每一个方格都考虑其上方和左边哪个更大,把大的那个金额加到现在的这个方格,代码如下。

满分代码

注意!!!我在之前就发现用变量定义的二维数组在初始化时必须使用双层的for循环,这次也是一样,而且必须全都初始化了结果才不会错。

#include <stdio.h>

int main(void){
	int n;
	scanf("%d",&n);
	int a[n+1][n+1];
	
	int i=0,j=0;
	for(i=0;i<=n;i++){
		for(j=0;j<=n;j++)
			a[i][j]=0;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	}
	
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++)
			a[i][j]+=  a[i][j-1]>a[i-1][j] ? a[i][j-1]:a[i-1][j];
	}
	
	printf("%d",a[n][n]);
	return 0;
}

最后,种一棵树最好的时机是在十年前,第二好的时机是现在。