ACM模版

描述

题解

经典的动态规划。

代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXN = 505;

int map[MAXN][MAXN] = {
  0};
int dp[MAXN][MAXN] = {
  0};

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            scanf("%d", map[i] + j);
        }
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] + map[i][j] : dp[i][j - 1] + map[i][j];
        }
    }

    cout << dp[N][N] << '\n';

    return 0;
}