信息学竞赛题，小学组，你不一定会做！题目：小猫希望获得奖品的总值最大是多少？

Question

小猫在玩一个淘宝游戏:在一个神奇的国度里，土地被划分成n×n的网格(1
≤n≤100)，每个格子里写有一个数x(1≤x≤100)，途径该格子的人会得到价 值x的奖品。现在小猫在左上角(1,1)，需要走到右下角(n,n)，他每一步只能向 右走一格或向下走一格。小猫希望获得奖品的总值最大，希望你能编程帮他解决 这个问题。
【输入文件】
文件名:walk.in。
第一行包含一个整数 n，表示网格的规模。
接下来 n 行，每行 n 个数，表示各个格子里的奖品价值。第 1 行第 1 个数表
示左上角，第 n 行第 n 个数表示右下角。
【输出文件】
文件名:walk.out。
仅包含一个整数，为小猫获得奖品的最大总价值。
【样例输入】
5
9 8 9 5 6
8 1 8 5 5
5 4 4 9 7
8 1 9 9 8
3 2 1 3 1
【样例输出】
66

Answer 1

这种题目对于小学生来说是比较难，不过对于成年人来说，没有难度。但是都发到网上代做，还有什么意义？

// Q717701.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "stdio.h"
#include "stdlib.h"

int solve(int x, int y, int * arr, int n)
{
    if (x == n - 1 && y == n - 1) return arr[x * n + y];
    if (x == n - 1) return solve(x, y + 1, arr, n) + arr[x * n + y];
    if (y == n - 1) return solve(x + 1, y, arr, n) + arr[x * n + y];
    int a = solve(x, y + 1, arr, n);
    int b = solve(x + 1, y, arr, n);
    return (a > b ? a : b) + arr[x * n + y];
}

int main()
{
    int n;
    scanf_s("%d", &n);
    int * arr = (int *)malloc(n * n * sizeof(int));
    for (int i = 0; i < n * n; i++)
        scanf_s("%d", &arr[i]);
    int r = solve(0, 0, arr, n);
    printf("%d\n", r);
    return 0;
}