小码农

趣味编程-面向每个人的创意编程
资源限制
内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s
问题描述
  有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
输入格式
  第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。
输出格式
  最多能拿金币数量。
样例输入
3
1 3 3
2 2 2
3 1 2
样例输出
11
数据规模和约定
  n<=1000
参考代码:
#include <stdio.h>
#include <math.h>
#define N 1001
int a[N][N];
int main()
{
   int i,j,n,add;
   scanf("%d",&n);
   for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
   	a[1][0]=a[0][1]=0;
   	for(i=1;i<=n;i++)
   	for(j=1;j<=n;j++)
   	{
   		if(a[i][j-1]>a[i-1][j])
   		a[i][j]+=a[i][j-1];
   		else
   		a[i][j]+=a[i-1][j];
       }
      add=a[0][3];
       for(i=2;i<=n;i++)
       if(a[n][i]>add)
       add=a[n][i];
       printf("%d",add);
       return 0;
 }
发表评论