2 条题解
-
0曾致瑜 (zengzhiyu) LV 7 @ 2023-1-28 21:29:30
/* DP的基础问题,题目稍有错误,但不影响做题。 DP基本思想:划分子问题确定状态与状态之间的转移关系,使用递推或记忆化搜索等方法解决问题 题目中说可以走向相邻的点,实际是可以走向下面的点和下面的右边的点。 */ #include<iostream> using namespace std; int x[12][12],dp[12][12]; /* x[i][j]代表数塔中第i层第j个位置上的元素 dp[i][j]代表从第i层第i层第j个位置上走到底层的数字最大之和 */ int main() { int a; cin>>a; for(int i=1;i<=a;i++) { for(int j=1;j<=i;j++) { cin>>x[i][j];//输入 dp[i][j]=x[i][j];//初始化dp数组 } } for(int i=a-1;i>=1;i--) { for(int j=1;j<=i;j++) { dp[i][j]=x[i][j]+max(dp[i+1][j],dp[i+1][j+1]); /* 动态转移方程:dp[i][j]=x[i][j]+max(dp[i+1][j],dp[i+1][j+1]); ↑ ↑ 下面的点 下面的右边的点 */ } } cout<<dp[1][1];//从顶层走到底层的最大值 }
-
-12022-9-21 21:48:18@
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[11][11]={0},i,j,n,ans=0; cin>>n; for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ cin>>a[i][j]; } } for(i=2;i<=n;i++){ for(j=1;j<=i;j++){ a[i][j]=max(a[i-1][j],a[i-1][j-1])+a[i][j]; } } for(int i=1;i<=n;i++){ ans=max(ans,a[n][i]); } cout<<ans; return 0;
}
- 1
信息
- ID
- 1259
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 47
- 已通过
- 19
- 上传者