Digital triangle model acwing 275. pass note

Digital triangle model AcWing 275. Pass slip

Original link

AcWing 275. Pass slip

Algorithm tags

Dynamic programming linear DP

Ideas

Optimization of row number value range

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];
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(),m=read();
    rep(i, 1, n+1){
        rep(j, 1, m+1){
            a[i][j]=read();  
        }
    }
    //  Sum of row and column values   The row determines the column 
    rep(k, 2, n+m+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<=m&&j2>=1&&j2<=m){
                    int t=a[i1][j1];
                    if(i1-i2){
                        t+=a[i2][j2];
                    }
                    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[n+m][n][n]);
    return 0;
}

Line number value range optimization 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];
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(),m=read();
    rep(i, 1, n+1){
        rep(j, 1, m+1){
            a[i][j]=read();  
        }
    }
    //  Sum of row and column values   The row determines the column 
    rep(k, 2, n+m+1){
        //  First time i That's ok 
        rep(i1, max(1ll, k-m), min(k, n)+1){
            //  Second time i That's ok 
            rep(i2, max(1ll, k-m), min(k, n)+1){
                // k-i1 Indicates the number of columns for the first time  k-i2 Indicates the number of secondary columns 
                int t=a[i1][k-i1];
                if(i1-i2){
                    t+=a[i2][k-i2];
                }
                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[n+m][n][n]);
    return 0;
}

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