原题链接:三角形
#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int main()
{
int n;
int k;
int h;
int i,j;
int tri[200][200]={0};
scanf("%d" , &n);
for(i=1;i<=n;i++)
{
scanf("%d" , &h);
for(k=1;k<=h;k++)
for(j=1;j<=k;j++) //将三角形数输入
scanf("%d" , &tri[k][j]);
for(k=h;k>=1;k--)
{
for(j=1;j<=k;j++)
{
tri[k][j]+=max(tri[k+1][j],tri[k+1][j+1]); //状态转移方程:根据要求,从底层开始,每一层加和下一层的值并取局部最优解此时满足,局部最优解,即为全局最优解所以当进行取值到最顶层时,此时最顶层的解即为全局最优解
}
}
printf("%d\n" , tri[1][1]);
memset(tri,0,sizeof(tri));
}
}
9.9 分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复