精华内容
下载资源
问答
  • 2022-03-19 20:43:57

    资源限制

    时间限制:1.0s 内存限制:256.0MB

    问题描述

    上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。

    路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外,向左下走的次数与向右下走的次数相差不能超过 1。

    输入格式

    输入的第一行包含一个整数N (1<N≤100),表示三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

    输出格式

    输出一个整数,表示答案。

    样例输入

    5
    7
    3 8
    8 1 0 
    2 7 4 4
    4 5 2 6 5

    Data

    样例输出

    27

    思路简介

    又是dp...,感觉蓝桥杯不如改名dp杯得了(bushi)...

    不是说蓝桥的题都是dp题,而是很多题都能用动态规划的方法,甚至可以说动态规划是算法界的半壁江山,所以学好动态规划非常重要,遇到一些题要习惯尝试dp。话不多说,开始解析此题:

    首先看图以及题,题干中所说的左下和右下,是对于图而言的。所以当我们用二位数组来存数据的时候,应该对应的是下方和右下。那么怎么用动态规划来解决此题呢?

    不妨先设f[i][j]表示i点到达j点的最大权值之和,那么怎么算呢?那就考虑对于每个i,j点,是怎么到达的。

    既然我们每次都能往下和右下走,即对于每个i j点能走到i+1,ji+1,j+1点。所以每个i j点应该是由i-1,ji-1,j-1点走来的。

    所以便找到了递推式,即所谓状态方程:f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j])。

    但是同样值得注意的是,题目中要求向下的次数和向右下的次数只差不能超过1。先以样例为例吧,n为5,走到底层需要4步,其实显然这四步一定是走了俩次向下两次向右下,因为往下走并不改变方向,所以相当于走了四次向下,两次向右,所以最终是走到了底层中间的位置。偶数同理,例如n为4,走到底层需要 3步,那么可以是两次向下一次右下,或一次向下两次右下,相当于走了三次下,一次右或者两次右,所以当是偶数时,最大值便取决于最底层中间的两个数的较大值。其实推广到n为任何的奇数或者偶数,此结论显然都是成立的,所以只要判断n的奇偶再输出便可。

     

    if (n & 1)//如果是奇数的话
            printf("%d", f[n][n / 2 + 1]);
        else
            printf("%d", max(f[n][n / 2 + 1], f[n][n / 2]));

     那么n&1是什么意思?下面简单介绍一下:

    显然整数不仅包括0和正整数,而且也包括负整数,这种方式如果是根据取余结果来判断是否为0来判断偶数、偶数的话无论正负显然都成立,但是如果用1来判定是否是奇数在某些情况下就欠妥了(因为负奇数对2取余结果为-1)。其实将整数用二进制表示后,可以很方便的进行奇偶性的判断,因为偶数,无论是正整数还是负整数,二进制表示时其最低位为0奇数,无论是正整数还是负整数,二进制表示时其最低位都为1,利用这一特性,可以非常方便快速的完成判断。

    n&1,即和1进行&操作,显然1的二进制除了第一位是1,其它位都0,如果是奇数的话,第一位是1。和1进行&后,只有1&1为1,其他结果都是0,所以显然奇数n&1后结果为1.同理,偶数n&1为0,从而快速精准判断n的奇偶性。

    AC代码如下

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 110;
    int a[N][N], f[N][N], n;
    int main()
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                scanf("%d", &a[i][j]);
        f[1][1] = a[1][1];//初始化
        for (int i = 2; i <= n; i++)//从第二行开始往下更新
            for (int j = 1; j <= i; j++)//对于每一行每一位都是如此更新权值
             f[i][j] = max(f[i - 1][j] + a[i][j], f[i - 1][j - 1] + a[i][j]);
        if (n & 1)//如果是奇数的话
            printf("%d", f[n][n / 2 + 1]);
        else
            printf("%d", max(f[n][n / 2 + 1], f[n][n / 2]));
        return 0;
    }

    其实这题也可以尝试深搜,但是显然很容易TLE,可以通过一些优化来省去不必要的搜索,如当

    abs(R-L)-(n-x)>1,n-x即剩下还要走几步,R-L的差的绝对值如果比n-x还要大1,那么剩下的几步全走某一个方向都没法弥补,没法使得R和L的绝对值只差<=1了,那么就不用搜索。还可以通过奇偶性优化等等。以下列出AC了一半的dfs代码,我就懒得优化了...(谁让dp这么好用)

    #include<bits/stdc++.h>
    using namespace std;
    int wk[2][2] = { {1,1}, {1,0} };//向右下走和向下
    int n, a[110][110];
    int vis[110][110], maxn;
    inline int read(){
    	char ch=getchar();int x=0,f=1;
    	while(ch<'0'||ch>'9'){
    		if(ch=='-')f=-1;
    		ch=getchar();
    	}
    	while(ch>='0'&&ch<='9'){
    		x=x*10+ch-'0';
    		ch=getchar();
    	}return x*f;
    }
    void dfs(int x, int y, int sum, int R, int L) {//现在的位置是x,y,总权值是sum 往右走了R步,往左走了L步
    	if (x == n){//到达最底层
    		if(abs(R-L)<=1)//说明结果合法 
    		maxn = max(maxn, sum);//更新最大值
    		return;
    	}
    	for (int i = 0; i < 2; i++) {//枚举两个个方向 
    		int tx = x + wk[i][0], ty = y + wk[i][1];//即将到达的坐
    			if(n-x-abs(R-L)<-1)continue;
    		if (tx<1 || ty>n || ty<1 || ty>n || vis[tx][ty])continue;//边界条件
    		vis[tx][ty] = 1;//标记说明访问过
    		switch (i) {
    		case 0: {
    			dfs(tx, ty, sum + a[tx][ty], R+1, L );//向右下走
    			break;
    		}
    		case 1: {
    			dfs(tx, ty, sum + a[tx][ty], R , L+1);//向下走 相当于图中的向左下走 
    			break;
    		}
    		}
    		vis[tx][ty] = 0;//取消标记
    	}
    }
    int main(){
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i++) 
    		for (int j = 1; j <= i; j++)
    			a[i][j]=read(); 
    	vis[1][1]=1;
    	dfs(1,1,a[1][1],0,0);
    	printf("%d", maxn);
    	return 0;
    }

    更多相关内容
  • 蓝桥杯 数字三角形

    千次阅读 2018-03-28 14:47:25
    蓝桥杯 数字三角形问题描述 (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 径,使该路径所经过的数字的总和最大。 ●每一步可沿左斜线向下或右斜线向下走; ●1三角形行数≤...

    蓝桥杯 数字三角形
    问题描述
      (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
      径,使该路径所经过的数字的总和最大。
      ●每一步可沿左斜线向下或右斜线向下走;
      ●1<三角形行数≤100;
      ●三角形中的数字为整数0,1,…99;


       .
      (图3.1-1)
    输入格式
      文件中首先读到的是三角形的行数。

      接下来描述整个三角形
    输出格式
      最大总和(整数)
    样例输入
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    样例输出
    30
    解析:这是一道动态规划类型的题目,具体代码如下:
    #include<iostream>  
    #include<string.h>// memset()函数的头文件 
    using namespace std;  
    int main()  
    {  
       int a[101][101];
       memset(a,0,sizeof(a));//把数组初始化为0 
       int n,sum=0;;
       cin>>n;
       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]);
       	if(a[i][j]>sum)
       	sum=a[i][j];
       }
       cout<<sum;
    }  

    展开全文
  • 题目要求:问题描述 (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。●每一步可沿左斜线向下或右斜线向下走;●1三角形行数≤100;●三角形中的...

    题目要求:

    问题描述   (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路

    径,使该路径所经过的数字的总和最大。

    ●每一步可沿左斜线向下或右斜线向下走;

    ●1<三角形行数≤100;

    ●三角形中的数字为整数0,1,…99;

    QjiuIn.do?fid=9RdAy6Be.

    (图3.1-1) 输入格式   文件中首先读到的是三角形的行数。

    接下来描述整个三角形 输出格式   最大总和(整数) 样例输入 5

    7

    3 8

    8 1 0

    2 7 4 4

    4 5 2 6 5 样例输出 30 --------------------------------------------------------分割线--------------------------------------------------------------

    解题思路:

    采用记忆化搜索的方法。

    要求计算从顶到底的能经过的最大数字和,

    假如从顶向下,逐个比较,复杂度很大,并不知道最后哪一个数字为终点,

    不妨逆向思维,从低向上,因为不论怎么走,第一个元素肯定是要经过的,不妨让他为路径终点,从最底层开始,逐步往上更新数字

    每个位置的数字变成了该位置向下或斜下数字的最大数再加上当前位置数字的和,既可到达当前位置的最大数字和

    如图

    java

    import java.util.Scanner;

    public class Main {

    public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[][] a = new int[n][n];

    for(int i = 0;i < n;i++)

    for(int j = 0;j <= i;j++){

    a[i][j] = sc.nextInt();

    }

    for(int i = n-2;i >= 0;i--)

    for(int j = 0;j <= i;j++)

    a[i][j] += Math.max(a[i+1][j], a[i+1][j+1]);

    System.out.println(a[0][0]);

    }

    }

    展开全文
  • 蓝桥杯 数字三角形 Python实现 问题描述  (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  径,使该路径所经过的数字的总和最大。  ●每一步可沿左斜线向下或右斜线向下走;  ...

    蓝桥杯 数字三角形 Python实现

    问题描述
      (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
      径,使该路径所经过的数字的总和最大。
      ●每一步可沿左斜线向下或右斜线向下走;
      ●1<三角形行数≤100;
      ●三角形中的数字为整数0,1,…99;在这里插入图片描述
    输入格式
      文件中首先读到的是三角形的行数
      接下来描述整个三角形
    输出格式
      最大总和(整数)
    样例输入
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    样例输出
    30

    我还是先说一下我的基本学习情况吧,没学过Python的数据结构,对算法啥的脑子就是一团浆糊。这道题就是考动态规划嘛,我还是一如既往地菜,在网上看思路,然后自己写写改改代码。求看到这篇文章的大佬们指教。
    这里有两个代码。
    一个基本就是粘贴的,原代码链接在这里。它原本的代码有点错误,编译错误加上结果也错,结果不一样好像因为不是一道题吧,稍微改一下就好。就是第5行构建dp数组那里和最后输出的s不是最大。改了之后竟然只能通过一个样例。。所以才有第二个代码。。

    n = eval(input())
    ls = []
    for i in range(n):
        ls.append(list(map(int, input().split())))
    dp = [[0 for _ in range(2*n-1)] for _ in range(n)]  # 构建DP数组,初始为0
    k = n-1      # 顶部数据的下标
    res = [[k]]  # 存储各个数据的下标
    for i in range(n-1):
        q = []   # 当前层的下标
        for j in range(len(res[-1])):
            q.append(res[-1][j]-1)
            q.append(res[-1][j]+1)
        res.append(list(set(q)))  # 除去重复的下标
    dp[0][k] = ls[0][0]           # 将顶部数据导入相应的下标的dp数组中
    for i in range(1,n):          # 横向坐标
        for j in range(len(ls[i])):
        # ls为存储的输入值,res为值相对于的在dp中的下标故len(ls) == len(res)
        # 分边界处理res[i][j]为取出相应的下标, dp[i][res[i][j]]为当前的值
            if j == 0:
                dp[i][res[i][j]] = dp[i-1][res[i][j]+1]+ls[i][j]
            elif j > 0 and j < len(ls[i])-1:            
                dp[i][res[i][j]] = max(dp[i-1][res[i][j]-1], dp[i-1][res[i][j]+1])+ls[i][j]
            else:
                dp[i][res[i][j]] = dp[i-1][res[i][j]-1]+ls[i][j]
    print(max(dp[-1]))
    

    第二个代码是我自己写的,参考这位大哥的C代码,我给改写了成Python了,非常地简短,非常地elegant。。但是无语子啊,7个样例就有一个过不去。

    n = eval(input())
    ls = []
    for i in range(n):
        ls.append(list(map(int, input().split())))
    for i in range(1,n):
        for j in range(i):
            if j == 0:
                ls[i][j] += ls[i-1][0]
            else:   
                ls[i][j] += max(ls[i-1][j-1],ls[i-1][j])
    print(max(ls[-1]))
    
    展开全文
  • 蓝桥杯 数字三角形 dp

    2022-03-22 22:46:36
    原题链接:蓝桥杯 数字三角形 对于题意中“向左下走的次数与向右下走的次数相差不能超过 1”的理解: 当n为奇数时,只有最后一行(奇数个数)的最中间一个数可以作为终点; 当n为偶数时,只有最后一行(偶数个数...
  • 试题 历届试题 数字三角形 提交此题 评测记录 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条...
  • 蓝桥杯数字三角形

    2022-04-03 18:08:21
    上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个...
  • 蓝桥杯 数字三角形(java题解)

    千次阅读 2016-06-02 09:36:16
     (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  径,使该路径所经过的数字的总和最大。  ●每一步可沿左斜线向下或右斜线向下走;  ●1三角形行数≤100;  ●三角形中的...
  • 题目 原题传送门 代码 #include<bits/stdc++.h> #define MAX 101 using namespace std; int n; int a[MAX][MAX]={0}; int res=-1;...void dfs(int hang,int lie,int left,int right,int sum) ...
  •  (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  径,使该路径所经过的数字的总和最大。  ●每一步可沿左斜线向下或右斜线向下走;  ●1三角形行数≤100;  ●三角形中的数字...
  • 蓝桥杯-数字三角形

    千次阅读 2019-03-22 15:49:10
     (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  径,使该路径所经过的数字的总和最大。  ●每一步可沿左斜线向下或右斜线向下走;  ●1三角形行数≤100;  ●三角形中的数字...
  • 这样就必定不会走那里,也就等效于没有,但是我们代码就变得好写了(不用判断是否有左上或右上) dp[i][j][k]=max(dp[i-1][j][k-1],dp[i-1][j-1][k+1])+arr[i][j] #arr[i][j]为三角形中i行j列的值 初始化: 在这里,...
  • 上图给出了一个数字三角形,从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你需要找到最大的路径和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数...
  • 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个...
  • 8. 数字三角形 【问题描述】 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。 对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最 大的和。 路径上的每一步只能从一个数...
  • public class Main { static int dr = 0;//向下+1,向右下-1 static int max = 0; static int N; static int[][] matrix; public static void main(String[] args) throws IOException { ... dfs, dr={-1,0,1} ...
  • 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个...
  • 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个...
  • 蓝桥杯 数字三角形(简单DP)

    千次阅读 2016-02-06 21:04:16
    算法训练 数字三角形 时间限制:1.0s 内存限制:256.0MB   问题描述  (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  径,使该路径所经过的数字的总和最大。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,165
精华内容 1,266
关键字:

蓝桥杯数字三角形