解题思路:
层数的范围<=1000,且走到一个点的最大值与走到更后面的最大值无关(即无后效性),可考虑开二维数组动态规划递推。
走到任意一点(i,j)累积的最大值可视为(i-1,j-1)或(i-1,j)的最大值与该位置的和。
设置两个二维数组拉满[1005][1005],a存储该位置值,b存储从开头到给位置累计最大值。
每一个b[i][j]=max(b[i-1][j],b[i-1][j-1])+a[i][j];
最后过一遍b的最后一行(即b[N][i]),找到最大值输出即为答案。
参考代码:
#include
using namespace std;
int N,a[1005][1005],b[1005][1005]; //定义数组与总行数
int ans=-2; //题目仅给出各店为非负数,防止特殊情况,将ans设为负数
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
} //输入
b[1][1]=a[1][1]; //先将第一个b[1][1]赋值
for(int i=2;i<=N;i++) //从第二行开始
{
for(int j=1;j<=i;j++)
{
b[i][j]=max(b[i-1][j],b[i-1][j-1])+a[i][j]; //每一个位置找最大累加和
}
}
for(int i=1;i<=N;i++)
{
ans=max(ans,b[N][i]);
} //搜索b的最后一行,找最大值,即为答案
cout<<ans<<endl;
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:749 |
C二级辅导-同因查找 (C语言代码)浏览:661 |
C语言程序设计教程(第三版)课后习题9.2 (Java代码)浏览:611 |
C语言训练-大、小写问题 (C语言代码)浏览:612 |
哥德巴赫曾猜测 (C语言代码)浏览:2320 |
出圈】指针malloc版浏览:355 |
DNA (C语言代码)浏览:391 |
DNA (C语言代码)浏览:747 |
C二级辅导-同因查找 (C语言代码)浏览:565 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:950 |