Title Description

Obuchi and Xiaoxuan are good friends and classmates. They always have endless topics together. In a quality development activity, the students in the class arranged to sit in a matrix with mm rows and nn columns, while Obuchi and Xiaoxuan were arranged at both ends of the diagonal of the matrix. Therefore, they could not talk directly. Fortunately, they can communicate by passing notes. The note has to be passed to each other through many students. Obuchi sits in the upper left corner of the matrix, coordinates (1,1) (1,1), and Xiaoxuan sits in the lower right corner of the matrix, coordinates (m,n)(m,n). The note from Xiaoyuan to Xiaoxuan can only be passed down or right, and the note from Xiaoxuan to Xiaoyuan can only be passed up or left.

During the activity, Obuchi hopes to pass a note to Xiaoxuan and hope Xiaoxuan will reply to him. Each student in the class can help them pass, but will only help them once. That is to say, if this person helps when Xiaoxuan hands Xiaoxuan the note, he will not help when Xiaoxuan hands it to Xiaoyuan. vice versa.

Another thing to note is that each student in the class is willing to help with varying degrees of favor (Note: the degree of kindness of Obuchi and Xiaoxuan is not defined, and 00 is used for input). It can be expressed by a natural number in [0100] [0100]. The larger the number, the better. Obuchi and Xiaoxuan hope to find students with a high degree of kindness to help pass the note, that is, to find two transmission paths back and forth, so as to maximize the sum of the kindness of the students on these two paths. Now, please help Obuchi and Xiaoxuan find these two paths.

Input format

The first row has two integers mm and nn separated by spaces, indicating that there are mm rows and nn columns in the class.

The next mm line is an m \times nm × n, the integer in row ii and column jj in the matrix represents the kindness of the students sitting in row ii and column jj. The nn integers in each line are separated by spaces.

Output format

The output file is an integer on one line, which represents the maximum sum of the kindness of the students involved in passing the note on the two roads back and forth.

Input and output samples

Enter #1 copy

3 3
0 3 9
2 8 5
5 7 0

Output #1 copy

34

Description / tips

[restrictions]

For 30% 30% data, 1 \le m,n \le 101 ≤ m,n ≤ 10;
For 100% and 100% data, it meets the following requirements: 1 \le m,n \le 501 ≤ m,n ≤ 50.

[source]

Question 3 of NOIP 2008 improvement group

Problem solving ideas

Because it is the path that two people can't get to each other, it can be seen as a person moving towards another person through two different paths.

At this time, in fact, the two paths start at the same time, which will appear when they reach the same point

It is better to use four-dimensional array to solve this kind of problem

The four-dimensional array has four states, namely

				num[i-1][j][p][q-1]
                num[i-1][j][p-1][q]
                num[i][j-1][p][q-1]
                num[i][j-1][p-1][q]

The equation of state is:

num[i][j][p][q]=arr[i][j]+arr[p][q]+max(num[i-1][j][p][q-1],max(num[i-1][j][p-1][q],max(num[i][j-1][p][q-1],num[i][j-1][p-1][q])));

Special condition judgment: when the two come to the same point:

//a[rri][j]==arr[p][q]				
                    if(i==p&&j==q)
                        dp[i][j][p][q]-=a[i][j];

The idea of this kind of problem is that (x,y) can only be reached from above and to the left

Dangdang ~ code is as follows

Of course, one more thing to note is: initialize the defined array

    memset(a,0,sizeof(a));
    memset(dp,0,sizeof(dp));

This should be because the value in the custom array is uncertain when it is not initialized

Another thing to be reminded is to distinguish whether the input matrix is a square matrix or an ordinary m*n matrix

//When the input has only one n-square matrix
for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int p=1;p<=n;p++)
            {
                for(int q=1;q<=n;q++)
                {
    cout<<dp[n][n][n][n]<<endl;
                    
//m*n matrix
for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int p=1;p<=m;p++)
            {
                for(int q=1;q<=n;q++)
                {
    cout<<dp[m][n][m][n]<<endl;                    
                    
                    

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int m,n;
    cin>>m>>n;
    int a[m+1][n+1];

    memset(a,0,sizeof(a));
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    int dp[m+1][n+1][m+1][n+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int p=1;p<=m;p++)
            {
                for(int q=1;q<=n;q++)
                {
                    //dp[i][j-1][p][q-1]
                    //dp[i][j-1][p-1][q]
                    //dp[i-1][j][p][q-1]
                    //dp[i-1][j][p-1][q]
                    dp[i][j][p][q]=max(dp[i][j-1][p][q-1],max(dp[i][j-1][p-1][q],max(dp[i-1][j][p][q-1],dp[i-1][j][p-1][q])))+a[i][j]+a[p][q];
                    if(i==p&&j==q)
                        dp[i][j][p][q]-=a[i][j];
                }
            }
        }
    }
    cout<<dp[m][n][m][n]<<endl;
    return 0;
}

Sprinkle flowers at the end~~