Digital triangle model acwing 1027. Grid retrieval

Digital triangle model AcWing 1027. Take the number of squares

Original link

AcWing 1027. Take the number of squares

Algorithm tags

DP linear DP

Ideas

Wrong thinking ： Go twice

Since there may be multiple solutions with the first time of travel , You can only choose one of them . But the first place you walk will be reset to 0, It is impossible to determine whether the value of the second time will be greater than the answer you have obtained when the first time is also the optimal solution and is not selected by you

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105;
int f[2*N][N][N], a[N][N];
int aa, b, c, d;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read();
    while(aa=read(), b=read(), c=read(), aa||b||c){
        a[aa][b]=c;
    }
    //  Sum of row and column values   The row determines the column 
    rep(k, 2, n+n+1){
        //  First time i That's ok 
        rep(i1, 1, n+1){
            //  Second time i That's ok 
            rep(i2, 1, n+1){
                // j1 It means the first time j Column  j2 It means the second time j Column 
                int j1=k-i1, j2=k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
                    int t=a[i1][j1];
                    //  Not the same path 
                    if(i1-i2){
                        t+=a[i2][j2];
                    }
                    //  Next   Lower right   The lower right   Right, right 
                    f[k][i1][i2]=max({f[k][i1][i2], f[k-1][i1-1][i2-1]+t, f[k-1][i1-1][i2]+t, f[k-1][i1][i2-1]+t, f[k-1][i1][i2]+t});
                }
            }
        } 
    }
    printf("%lld", f[2*n][n][n]);
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support