Topic link

On the first code .

Error code

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 12;
int n;
int G[N][N],f[N][N],D[N][N];
int main(){
    
    cin >> n;
    while(true){
    
        int x,y,v;scanf("%d%d%d",&x,&y,&v);
        if(!(x or y or v)) break;
        G[x][y] = v;
    }
    for(int i = 0;i <= n;i++) f[i][0] = f[0][i] = -1;
    f[1][0] = 0;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++){
    
            if(f[i][j-1] > f[i-1][j]) D[i][j] = 1;
            f[i][j] = max(f[i][j-1],f[i-1][j]) + G[i][j];
        }
    int x = f[n][n];
    int i = n,j = n;
    while(i != 0 and j != 0){
    
        G[i][j] = 0;
        if(D[i][j]) j --;
        else i--;
    }
    memset(f,0,sizeof f);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++){
    
            f[i][j] = max(f[i-1][j],f[i][j-1]) + G[i][j];
        }
    printf("%d",f[n][n] + x);
    return 0;
}

Correct code

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 12;
int n;
int G[N][N];
int f[2*N][N][N];
int main(){
    
    scanf("%d",&n);
    int x,y,v;
    while(~scanf("%d%d%d",&x,&y,&v) and (x or y or v)) G[x][y] = v;
    for(int k = 2;k <= 2 * n;k++){
    
        for(int i1 = 1;i1 <= n;i1++){
    
            for(int i2 = 1;i2 <= n;i2++){
     // (i1,k-i1) (i2,k-i2)
                int j1 = k - i1,j2 = k - i2;
                if(j1 >= 1 and j1 <= n and j2 >= 1 and j2 <= n){
    
                    int &x = f[k][i1][i2];
                    int t = G[i1][j1];
                    if(i1 != i2) t += G[i2][j2];
                    x = max(x,f[k-1][i1][i2] + t);
                    x = max(x,f[k-1][i1-1][i2] + t);
                    x = max(x,f[k-1][i1][i2-1] + t);
                    x = max(x,f[k-1][i1-1][i2-1] + t);
                }
            }
        }
    }
    printf("%d",f[2*n][n][n]);
    return 0;
}

Error code is one of our easiest ideas , That is, one person goes first , After a walk , Then update the number of the square chart . Then walk again , Add up the two maximum values obtained respectively , As the end result .
Error code exists wa The situation of .

What do you ask ？

Problem analysis

We made a sequence for walking , The first person who walks gets the most solution —— We set it as $x_1$, The optimal solution obtained by the second person is $x_2$. It's not hard to see. , For the global optimal solution $x$, We use greedy thinking directly , Assumed $x=x_1+x_2$.

Here comes a problem ,$x_1+x_2$ Whether it must be equal to $x$？

The answer is No .

As shown in the figure below ：


All numbers can be obtained through the two paths in Figure 1 .
And if the greedy method is used , That is, choose a path that can get the current local optimal solution for the first time , Then no matter how to take it the second time , You can't select all the remaining two numbers .

therefore , without doubt , For this question , The local optimal solution cannot deduce the global optimal solution .

therefore , We have to consider “ parallel ” Dynamic planning method .

Originality is not easy. , Thank you for your support .