Winalways @ 2024-11-24 11:57:40
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], dp[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> a[i][j];
}
}
int mans = 0;
dp[1][1] = a[1][1];
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]);
if (dp[i][j] > mans)
mans = dp[i][j];
}
}
cout << mans;
return 0;
}by WE_TRT @ 2024-11-28 15:12:56
#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],n;
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>=1;i--){
for(int j=1;j<=i;j++){
a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j];
}
}
cout<<a[1][1];
return 0;
}by WE_TRT @ 2024-11-28 15:18:14
@Winalways 在max的时候下一行是没有的,所以你需要反着推,并且先要把最后一行赋值给dp。