第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-124 数字三角形
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
数字三角形
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
示例中出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。
每一步可沿左斜线向下或右斜线向下走；
1＜三角形行数≤100；
三角形中的数字为整数0，1，…99；
输入格式
文件中首先读到的是三角形的行数。
接下来描述整个三角形
输出格式
最大总和（整数）
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
题解：
C语言
#include<stdio.h> int n,a[100][100]; int sum(); int main(){ int i,num,j; scanf("%d",&n); for(i=0;i<n;i++) { for(j=0;j<=i;j++) { scanf("%d",&num); a[i][j]=num; } } printf("%d",sum()); return 0; } /* int sum(int i,int j) { if(i==n) { return a[i][j]; } if(sum(i+1,j)>sum(i+1,j+1)) { return sum(i+1,j)+a[i][j]; }else { return sum(i+1,j+1)+a[i][j]; } } */ int sum() { int i,j; for(i=n-1;i>0;i--) { for(j=0;j<i;j++) { if(a[i][j]>a[i][j+1]) { a[i-1][j]+=a[i][j]; } else { a[i-1][j]+=a[i][j+1]; } } } return a[0][0]; }
C++语言
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main(){ int n; cin >> n; vector<vector<int> >a(n + 1, vector<int>(n + 1)); for (int i = 1; i <= n; i++){ for (int j = 1; j <= i; j++){ cin >> a[i][j]; } } for (int i = 1; i <= n; i++){ for (int j = 1; j <= i; j++){ a[i][j] = max(a[i - 1][j - 1], a[i - 1][j]) + a[i][j]; } } int max = a[n][1]; for (int i = 2; i <= n; i++){ if (a[n][i] > max) max = a[n][i]; } cout << max << endl; system("pause"); return 0; }
Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。
import java.io.*; public class Main { static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))) ; static int n ; static int [][] a ; public static void main(String[] args) { n = getInt(); a = new int[n][n] ; for( int i = 0 ; i < n ; i++ ) { for( int j = 0 ; j <= i ; j++ ) a[i][j] = getInt() ; } for( int i = n-1 ; i > 0 ; i-- ) { for( int j = 0 ; j < i ; j++ ) { if( a[i][j] > a[i][j+1] ) a[i-1][j] += a[i][j] ; else a[i-1][j] += a[i][j+1] ; } } System.out.println( a[0][0] ); } private static int getInt() { try { in.nextToken() ; } catch (IOException e) { e.printStackTrace(); } return (int) in.nval; } }
Python语言
相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。
n = int(input()) arr = [] for i in range(n): lis = list(map(int,input().split())) arr.append(lis) #print(arr) res = arr[:] #print(res) for i in range(n-2,-1,-1): for j in range(len(res[i])): res[i][j] = max(res[i+1][j],res[i+1][j+1])+res[i][j] print(res[0][0])
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
