2022-2-14 acwing1027 grid access

1027. Take the number of squares

Someone from the top left corner of the picture A set out , You can walk down , You can also walk to the right , Until we get to the bottom right B spot .

On the way , He can take the number of squares （ The removed squares will be changed to numbers 0）.

This person is from A Point to B I walked twice at 8 o'clock , Try to find two such paths , Make the sum of the obtained numbers the largest .

Compared with ordinary walk grid , Find the maximum path , The difference is ： Take two paths . therefore DP The dimension of increases , use 4 Dimension represents a current state .
And because the steps of the two paths are the same , So we can use the equivalence relationship to reduce the dimension ：k=i1+j1=i2+j2
The starting point ：2 A little bit
End ：2 A little bit
There will be duplication of two paths , Judge the repetition , Then add the corresponding weight .

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int grid[N][N]={
    0};
int dp[2*N][N][N]={
    0};
int main(){
    
    
    cin>>n;
    int a,b,c;
    while(1){
    
        cin>>a>>b>>c;
        if(a==0&&b==0&&c==0) break;
        grid[a][b]=c;
    }


    for(int k=2;k<=n+n;k++){
    
        for(int i1=1;i1<=n;i1++){
    
            for(int i2=1;i2<=n;i2++){
    
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
    
                    int value=grid[i1][j1];
                    if(i1!=i2) value+=grid[i2][j2];
                    int &x=dp[k][i1][i2];
                    x=max(dp[k-1][i1-1][i2-1]+value,x);
                    x=max(dp[k-1][i1-1][i2]+value,x);
                    x=max(dp[k-1][i1][i2-1]+value,x);
                    x=max(dp[k-1][i1][i2]+value,x);
                }
            }
        }
    }

    printf("%d",dp[2*n][n][n]);

}

275. Pass slip

Xiaoyuan and Xiaoxuan are good friends and classmates , They have a lot to talk about together .

In a quality development activity , The class arranged to sit in a m That's ok n Columns of the matrix , And Xiaoyuan and Xiaoxuan are arranged at both ends of the diagonal of the matrix , therefore , They can't talk directly .

Fortunately, , They can communicate by passing notes .

The note has to be passed to each other through many students , Xiaoyuan sits in the upper left corner of the matrix , coordinate (1,1), Xiaoxuan sits at the bottom right corner of the matrix , coordinate (m,n).

The note from Xiaoyuan to Xiaoxuan can only be passed down or to the right , The note from Xiaoxuan to Xiaoyuan can only be passed up or left .

In progress , Xiaoyuan hopes to deliver a note to Xiaoxuan , At the same time, I hope Xiaoxuan will reply to him .

Everyone in the class can pass it on for them , But only once , That is to say, if this person helps Xiaoxuan when Xiaoyuan hands him the note , Then when Xiaoxuan hands it to Xiaoyuan, he won't help again , vice versa .

One more thing to note , Everyone in the class is willing to help （ Be careful ： There is no definition of the degree of kindness of Xiaoyuan and Xiaoxuan , Input time 0 Express ）, You can use a 0∼100 It's a natural number , The greater the number, the better .

Xiaoyuan and Xiaoxuan hope to find students with high degree of kindness to help pass the notes , I.e. find two transfer paths back and forth , So that the sum of the two paths is the largest .

Now? , Please help Xiaoyuan and Xiaoxuan find such two paths .

Input format
The first line has 2 Integers separated by spaces m and n, Indicates that the student matrix has m That's ok n Column .

Next m Row is one. m×n Matrix , In matrix i That's ok j The integer representation of the column sits at i That's ok j The degree of kindness of the students , Per row n Integers separated by spaces .

Output format
Output an integer , Represents the maximum value of the sum of the kindness degree of the students participating in the transfer of the notes on the two routes back and forth .

Data range
1≤n,m≤50

AcWing 275. A code that proves why you can use a square to retrieve data in a note

The boss' explanation is very clear ~ If the two paths pass through repeated points , Then the weight of the repeated point for the second time must be 0, The weight obtained by detour is greater than or equal to 0, Therefore, it is enough to use the idea of grid counting to find out two paths and walk the number and the largest at the same time

Modify the previous question slightly according to the meaning of the question code that will do ：

#include<bits/stdc++.h>
using namespace std;
const int N=55;

int main(){
    
    int n,m;
    cin>>n>>m;
    int grid[N][N]={
    0};
    int dp[2*N][N][N]={
    0};
    int v;
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            cin>>v;
            grid[i][j]=v;
        }
    }



    for(int k=2;k<=n+m;k++){
    
        for(int i1=1;i1<=n;i1++){
    
            for(int i2=1;i2<=n;i2++){
    
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j1<=m&&j2>=1&&j2<=m){
    
                    int value=grid[i1][j1];
                    if(i1!=i2) value+=grid[i2][j2];
                    int &x=dp[k][i1][i2];
                    x=max(dp[k-1][i1-1][i2-1]+value,x);
                    x=max(dp[k-1][i1-1][i2]+value,x);
                    x=max(dp[k-1][i1][i2-1]+value,x);
                    x=max(dp[k-1][i1][i2]+value,x);
                }
            }
        }
    }

    printf("%d",dp[n+m][n][n]);

}