这还是一道简单题

这还是一道简单题

时间： 1ms        内存：128M

描述：

一个 N*N 矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。

例如：3 * 3 的方格。

    1 3 3

    2 1 3

    2 2 1

能够获得的最大价值为：11。

输入：

第1行：N，N为矩阵的大小。(2 <= N <= 500)

第 2 - N + 1 行：每行 N 个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000)

输出：

输出能够获得的最大价值。

示例输入：

3
1 3 3
2 1 3
2 2 1

示例输出：

11

提示：

参考答案（内存最优[1952]）：

#include<stdio.h>
#define max(a,b) a>b?a:b
int main()
{
    int a[501][501];
    int i,j,n,sum=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    scanf("%d",&a[i][j]);
    for(i=n-2;i>=0;i--)
      a[n-1][i]+=a[n-1][i+1];
    for(i=n-2;i>=0;i--)
      a[i][n-1]+=a[i+1][n-1];
     for(i=n-2;i>=0;i--)
     for(j=n-2;j>=0;j--)
      a[i][j]+=max(a[i+1][j],a[i][j+1]);
     printf("%d",a[0][0]);
    return 0;
}

参考答案（时间最优[32]）：

#include<stdio.h>
#define max(a,b) a>b?a:b
int main()
{
    int a[501][501];
    int i,j,n,sum=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    scanf("%d",&a[i][j]);
    for(i=n-2;i>=0;i--)
      a[n-1][i]+=a[n-1][i+1];
    for(i=n-2;i>=0;i--)
      a[i][n-1]+=a[i+1][n-1];
     for(i=n-2;i>=0;i--)
     for(j=n-2;j>=0;j--)
      a[i][j]+=max(a[i+1][j],a[i][j+1]);
     printf("%d",a[0][0]);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。