1. #include<stdio.h>
  2. #include<string.h>
  3. int max(int a,int b)
  4. {
  5. if(a>b)return a;
  6. return b;
  7. }
  8. int main()
  9. {
  10. int n;
  11. int k;
  12. int h;
  13. int i,j;
  14. int tri[200][200]={0};
  15. scanf("%d" , &n);
  16. for(i=1;i<=n;i++)
  17. {
  18. scanf("%d" , &h);
  19. for(k=1;k<=h;k++)
  20. for(j=1;j<=k;j++) //将三角形数输入
  21. scanf("%d" , &tri[k][j]);
  22. for(k=h;k>=1;k--)
  23. {
  24. for(j=1;j<=k;j++)
  25. {
  26. tri[k][j]+=max(tri[k+1][j],tri[k+1][j+1]); //状态转移方程:根据要求,从底层开始,每一层加和下一层的值并取局部最优解此时满足,局部最优解,即为全局最优解所以当进行取值到最顶层时,此时最顶层的解即为全局最优解
  27. }
  28. }
  29. printf("%d\n" , tri[1][1]);
  30. memset(tri,0,sizeof(tri));
  31. }
  32. }
点赞(0)
 

9.9 分

1 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论