HZNU 与班尼特·胡迪一起攻破浮空城 【DP】

题目链接

http://acm.hznu.edu.cn/OJ/problem.php?id=2264

思路

从终点往起点走 然后每次更新状态

因为要满足 最短路线

所以其实 只能是 往左走，往下走 或者 往下一层走

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;

const double E = exp(1);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 1e2 + 5;

const int MOD = 1e9 + 7;

int G[maxn][maxn][maxn];

int dp[maxn][maxn][maxn];

int main()

{

    int n, m, h;

    while (~scanf("%d%d%d", &n, &m, &h))

    {

        CLR(G);

        for (int k = 1; k <= h; k++)

        {

            for (int i = 1; i <= n; i++)

            {

                for (int j = 1; j <= m; j++)

                {

                    scanf("%d", &G[k][i][j]);

                }

            }

        }

        CLR(dp);

        for (int k = h; k >= 1; k--)

        {

            for (int i = 1; i <= n; i++)

            {

                for (int j = m; j >= 1; j--)

                {

                    dp[k][i][j] = max(max(dp[k + 1][i][j], dp[k][i - 1][j]), dp[k][i][j + 1]) + G[k][i][j];

                }

            }

        }

        cout << dp[1][n][1] << endl;

    }

}