xingjielongSYH @ 2024-10-01 09:24:49
#include<bits/stdc++.h>
using namespace std;
int a[2000][2000];
int dp[2000][2000];
int n;
int dfs(int x,int y){
if(y>x || y==0 || x==0)return 0;
if(dp[x][y])return dp[x][y];
dp[x][y]=max(dfs(x-1,y),dfs(x-1,y-1))+a[x][y];
return dp[x][y];
}
int dt(){
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> a[i][j];
}
}
int ans=0;
dt();
for(int i=1;i<=n;i++){
ans=max(dp[n][i],ans);
}
cout << ans<<endl;
return 0;
}搞了递推和递归两条，递归_8TLE，递推全RE\ 求调
by xingjielongSYH @ 2024-10-01 09:25:21
测试数据没问题
by CMWabc123 @ 2024-10-01 09:28:02
#include <iostream>
#include <cmath>
using namespace std;
int n,a[1010][1010];
int 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-1; i>0; i--) {
for(int j=1; j<=i; j++) {
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
}
}
cout<<a[1][1];
return 0;
}直接输出dp[1][1]吧
by xingjielongSYH @ 2024-10-01 09:32:44
@CMWabc123 懂了，谢谢