解题思路: 问题的解析:关于求最大值问题也就是求最优值问题,不可以采用贪心算法,贪心算法只能得到局部最优
现在开始对问题本身进行分析,这类问题可以从算法设计于分析一书中动态规划一章的求最短海岛路径类推。
先考虑使用回溯法,会发现时间复杂度大概为O(n!),必然发生超时现象。
而当我们从三级性最后一层逐步返回最大值时时间复杂度为0(n^2)是满足测评通过的。
一下是代码实列:
注意事项:
参考代码:#include<iostream>
using namespace std;
int num[100][100]={0};//本题中因为三角形最大为100层。
int main()
{
int T;
cin>>T;
for(int i=1;i<=T;i++)
{
int N;
cin>>N;
for(int j=0;j<N;j++)
for(int k=0;k<=j;k++)//三角型的输入
{
int t;
cin>>t;
num[j][k]=t;
}
for(int j=N-1;j>0;j--)
{
for(int k=0;k<j;k++)//从最低层开始返回
{
if(num[j][k]<num[j][k+1])//比较左右两边将最大的一个返回至上一层。
num[j-1][k]+=num[j][k+1];
else
num[j-1][k]+=num[j][k];
}
}
cout<<num[0][0]<<endl;//最后第一个数就是最大的值,该算法缺点是会将三角形中除最后一层所有的值都发生了改变。
}
}
0.0分
0 人评分
【蟠桃记】 (C语言代码)浏览:2222 |
汽水瓶 (C语言代码)浏览:704 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:662 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:468 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:762 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:575 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:507 |
C语言训练-列出最简真分数序列* (C语言代码)浏览:616 |
WU-输出九九乘法表 (C++代码)浏览:1671 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:1341 |