首页 > 试题广场 >

三角形取数(Hard Version)

[编程题]三角形取数(Hard Version)
  • 热度指数：1367 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个由 n 行构成的数字三角形。第 i 行共有 2i-1 个整数，整体形状如下图所示（以 n=3 为例）：



\hspace{15pt}从顶点（第一行唯一的数字）出发，依次向下移动恰好 n-1 次直到抵达最后一行。
\hspace{15pt}假设当前位于第 i 行第 j 列：
{\hspace{20pt}}_\texttt{1.}\,可以向正下方移动至第 (i+1) 行第 j 列；
{\hspace{20pt}}_\texttt{2.}\,可以向左下方移动至第 (i+1) 行第 (j-1) 列；
{\hspace{20pt}}_\texttt{3.}\,可以向右下方移动至第 (i+1) 行第 (j+1) 列。

\hspace{15pt}每到达一个位置都会获得该位置的数值。定义在整个行走过程中，向左下方移动的次数记为 l，向右下方移动的次数记为 r。我们需要满足


\left|l-r\right|\leqq k



\hspace{15pt}请你选择一条合法路径，使得获得数值之和最大，并输出该最大值。

输入描述:
\hspace{15pt}在一行上输入两个整数 n,k\left(1\leqq n\leqq 300;\ 0\leqq k\leqq n\right)，分别表示数字三角形的行数与允许的移动差。 
\hspace{15pt}此后 n 行，第 i 行输入 2i-1 个整数 

a_{i,1},a_{i,2},\dots ,a_{i,2i-1}\left(-2\times10^9\leqq a_{i,j}\leqq 2\times10^9\right)

\hspace{15pt}共计 \displaystyle\sum_{i=1}^{n}(2i-1)=n^2 个整数。


输出描述:
\hspace{15pt}输出一个整数，表示满足条件的路径可以取得的最大数值之和。
示例1

输入

3 1
1
2 3 4
5 6 7 8 9

输出

13

说明

\hspace{15pt}在该样例中，可选取的最大路径为 
\hspace{23pt}\bullet\,第 1 行：取 1； 
\hspace{23pt}\bullet\,第 2 行：向右下方移动，取 4； 
\hspace{23pt}\bullet\,第 3 行：向正下方移动，取 8。 
\hspace{15pt}总和为 1+4+8=13，且 \left|l-r\right|=1\leqq 1。
示例2

输入

3 0
1
2 3 4
5 6 7 8 9

输出

12
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-08-11 17:42:34
题目链接 三角形取数(Hard Version) 题目描述 给定一个 行的数字三角形，从顶点出发，每次可以向正下方、左下方或右下方移动，直到抵达最后一行。要求在整个过程中，向左下方移动的次数 和向右下方移动的次数 的差的绝对值不超过一个给定的整数 ，即 。目标是找到一条满足此条件的路径，使得路 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 牛客295096510号
发表于 2025-07-25 09:51:09
inp=input().split(' ') n,k=int(inp[0]),int(inp[1]) num_mat=[] all_num=[] for i in range(n): tar=input().split(' ') target=[int(x) for x in ta 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 BraveCoder
发表于 2025-09-26 11:54:38
import java.util.Scanner; public class Main { public static void main(String[] args) { final long INF = -1_000_000_000_000_000_000L; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 甘肃农业大学_zrk
发表于 2025-10-18 17:46:15
/*#include <bits/stdc++.h> using namespace std; long long int a[305][605]={0}; bool isa[305][605]={0}; long long int dp[305][305][305]={0}; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 ZYCwuque
发表于 2025-08-23 11:35:40
import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub long INF=-10000000000 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 励偲
发表于 2025-10-13 00:16:13
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async ():P 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 冷艳的西红柿刷牛客
发表于 2025-10-09 14:09:27
import java.util.Arrays; import java.util.Scanner; /** * @author supermejane * @date 2025/10/9 12:00 * @description BGN69 三角形取数(Hard Version) */ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 icepointboy
发表于 2025-10-27 15:54:35
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin &g 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：华为机试编程模拟题4
难度：
3条回答 511浏览

热门推荐

相关试题

三角形取数(Hard Version)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号