Digital triangle model acwing 1018. Minimum toll

Digital triangle model AcWing 1018. Minimum tolls

Original link

AcWing 1018. Minimum tolls

Algorithm tags

DP linear DP

Ideas

From the meaning of the title , Time spent should be less than (2N−1) , So you can't go back , Similar to the problem of picking peanuts .

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, INF = 0x3f3f3f3f;
int f[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();
	rep(i, 1, n+1){
	    rep(j, 1, n+1){
	        a[i][j]=read();
	    }
	}
	rep(i, 1, n+1){
	    rep(j, 1, n+1){
	        if(i==1&&j==1){
	            f[i][j]=a[i][j];
	        }else{
	            f[i][j]=INF;
	            if(i>1){
	                f[i][j]=min(f[i][j], f[i-1][j]+a[i][j]);
	            }
	            if(j>1){
	                f[i][j]=min(f[i][j], f[i][j-1]+a[i][j]);    
	            }
	        }
	    }
	}
	printf("%lld", f[n][n]);
    return 0;
}

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