The best riding route用 C 语言实现的最佳办法

Question

Problem Description
As a cheap labor in a small company, LL has to ride back and forth between school and office every day. It is a tedious trip. So he want to design the most satisfactory riding route. After several day's experiment, he draw the simple map. It contains n*m areas. The school is in (0,0) while the office is in (n-1,m-1). He also record the scenery rank of each area A(i,j) and the time need to ride through each area B(i,j). ( For the start and end, A(0,0), B(0,0), A(n-1,m-1), B(n-1,m-1) are always 0. ) Now, LL defines the satisfactory degree of a round trip as follow:

                                   ∑{ A(i,j) | Area (i,j) is in the riding route (come or go). }

the satisfactory degree = ----------------------------------------------------------------------
∑{ B(i,j) | Area (i,j) is in the riding route (come or go). }

Attention: 1. LL doesn't want to make a detour. So, from school to office he only ride rightward or downward and from office to school only leftward or upward.
2. LL won't pass the same area in the whole round trip except the start and end.

Input
Each test case begins with two integers n,m ( 3<=n,m<=30 ), which is the size of the map. Then n lines follow, each contains m integers A(i,j). Another n lines follow, each contains m integers B(i,j). 1 <= A(i,j),B(i,j) <= 100.

Output
For each case, Output the maximal satisfactory degree he can get in a round trip.

Sample Input
3 3
0 1 2
3 4 5
6 7 0
0 7 6
5 4 3
2 1 0

Sample Output
13/11

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

这是一个典型的动态规划问题。我们可以将每个点看作是下一个阶段的起点或终点，然后使用一个二维数组dp[i][j]来表示从当前位置出发到下一个位置（包括当前位置）的满意程度。

首先，我们需要初始化dp矩阵，使得dp[0][0]=A[0][0]+B[0][0]和dp[n-1][m-1]=B[n-1][m-1]-A[n-1][m-1]。

然后，对于每一个点i，j，我们可以通过计算dp[i+1][j]和dp[i][j+1]的和得到满意程度。

最后，我们返回最大值作为答案。

以下是C++代码：

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> A(n, vector<int>(m));
    for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j)
            cin >> A[i][j];
    vector<vector<int>> B(n, vector<int>(m));
    cin >> n >> m;
    for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j)
            cin >> B[i][j];
    int ans = 0;
    for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j)
            ans = max(ans, A[i][j] + B[i][j]);
    cout << ans;
    return 0;
}

这个程序的时间复杂度是O(n^2 * m)，空间复杂度也是O(n * m)。