Eroi @ 2021-10-17 10:48:20
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
int x=0;
int f=1;
char ch;
ch=getchar();
while(ch>'9'||ch<'0'){
if(ch='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int a[1005][1005];
int r;
int mem[1005][1005];
int dp(int line,int i){
if(line==r){
return mem[line][i];
}
if(mem[line][i]>0) return mem[line][i];
return mem[line][i]=a[line][i]+max(dp(line+1,i),dp(line+1,i+1));
}
int main()
{
r=read();
for(int i=1;i<=r;i++){
for(int j=1;j<=i;j++){
a[i][j]=read();
}
}
memset(mem,0,sizeof(mem));
for(int i=1;i<=r;i++){
mem[r][i]=a[r][i];
}
cout<<dp(1,1);
return 0;
} by Skyboys @ 2023-07-28 21:22:31
递归会TLE 要递推 AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;
int n,a[N][N],dp[N][N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)cin>>a[i][j];
for(int i=n;i>=1;i--)
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
cout<<dp[1][1]<<endl;
return 0;
}