解题思路:
层数的范围<=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语言程序设计教程(第三版)课后习题12.2 (C语言代码)浏览:811 |
C语言训练-求矩阵的两对角线上的元素之和 (C语言代码)浏览:3396 |
C语言程序设计教程(第三版)课后习题8.1 (Java代码)浏览:782 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:377 |
C语言程序设计教程(第三版)课后习题6.3 (C++代码)浏览:963 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:408 |
Tom数 (C语言代码)浏览:527 |
分解质因数 (C++代码)浏览:1482 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:585 |
1250题解浏览:561 |