三角形取数(Hard Version)【牛客tracker 每日一题】

发布时间:2026/11/17 16:49:14

三角形取数(Hard Version)【牛客tracker  每日一题】 三角形取数(Hard Version)时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一个由n nn行构成的数字三角形。第i ii行共有2 i − 1 2i - 12i−1个整数整体形状如下图所示以n 3 n 3n3为例1 2 3 4 5 6 7 8 9从顶点第一行唯一的数字出发依次向下移动恰好n − 1 n - 1n−1次直到抵达最后一行。假设当前位于第i ii行第j jj列可以向正下方移动至第( i 1 ) (i 1)(i1)行第j jj列可以向左下方移动至第( i 1 ) (i 1)(i1)行第( j − 1 ) (j - 1)(j−1)列可以向右下方移动至第( i 1 ) (i 1)(i1)行第( j 1 ) (j 1)(j1)列。每到达一个位置都会获得该位置的数值。定义在整个行走过程中向左下方移动的次数记为l ll向右下方移动的次数记为r rr。我们需要满足∣ l − r ∣ ≤ k |l - r| \le k∣l−r∣≤k请你选择一条合法路径使得获得数值之和最大并输出该最大值。输入描述在一行上输入两个整数n , k ( 1 ≤ n ≤ 300 ; 0 ≤ k ≤ n ) n, k\ (1 \le n \le 300;\ 0 \le k \le n)n,k(1≤n≤300;0≤k≤n)分别表示数字三角形的行数与允许的移动差。此后n nn行第i ii行输入2 i − 1 2i - 12i−1个整数a i , 1 , a i , 2 , … , a i , 2 i − 1 ( − 2 × 10 9 ≤ a i , j ≤ 2 × 10 9 ) a_{i,1}, a_{i,2}, \dots, a_{i,2i-1} \quad \left(-2 \times 10^9 \le a_{i,j} \le 2 \times 10^9\right)ai,1​,ai,2​,…,ai,2i−1​(−2×109≤ai,j​≤2×109)共计∑ i 1 n ( 2 i − 1 ) n 2 \sum\limits_{i1}^{n} (2i - 1) n^2i1∑n​(2i−1)n2个整数。输出描述输出一个整数表示满足条件的路径可以取得的最大数值之和。示例 1输入3 1 1 2 3 4 5 6 7 8 9输出13说明在该样例中可选取得的最大路径为第1 11行取1 11第2 22行向右下方移动取4 44第3 33行向正下方移动取8 88。总和为1 4 8 13 1 4 8 1314813且∣ l − r ∣ 1 ≤ 1 |l - r| 1 \le 1∣l−r∣1≤1。示例 2输入3 0 1 2 3 4 5 6 7 8 9输出12数据范围与提示1 ≤ n ≤ 300 1 \le n \le 3001≤n≤3000 ≤ k ≤ n 0 \le k \le n0≤k≤n− 2 × 10 9 ≤ a i , j ≤ 2 × 10 9 -2 \times 10^9 \le a_{i,j} \le 2 \times 10^9−2×109≤ai,j​≤2×109三角形中共有n 2 n^2n2个整数核心思路动态规划。设d p [ i ] [ j ] [ d ] dp[i][j][d]dp[i][j][d]表示走到第i ii行第j jj列、且当前l − r d l - r dl−rd时能获得的最大数值之和d dd加上偏移量n nn以避免负数下标。转移时由上一行的( j − 1 ) (j-1)(j−1)、j jj、( j 1 ) (j1)(j1)三个位置推来并相应地让d dd减1 11左下方或加1 11右下方。由于每步只改变1 11且最终要求∣ l − r ∣ ≤ k |l-r| \le k∣l−r∣≤k只需保留d ∈ [ − k , k ] d \in [-k, k]d∈[−k,k]的状态。状态数O ( n 3 ) O(n^3)O(n3)配合n ≤ 300 n \le 300n≤300可以接受。注意元素可能为负d p dpdp需初始化为极小值如− 10 18 -10^{18}−1018量级并优先使用long long防止溢出。解题思路本题是数字三角形上的动态规划问题。给定一个n nn行的数字三角形第i ii行有2 i − 1 2i-12i−1个整数。从顶点出发向下移动恰好n − 1 n-1n−1次到达最后一行每步可走正下方、左下方或右下方。设左下方移动次数为l ll右下方移动次数为r rr要求∣ l − r ∣ ≤ k |l-r| \le k∣l−r∣≤k求路径上数字之和的最大值。1. 问题等价转化将三角形按行优先顺序展成一维数组第i ii行1 ≤ i ≤ n 1 \le i \le n1≤i≤n占据索引( i − 1 ) 2 1 (i-1)^21(i−1)21到i 2 i^2i2共2 i − 1 2i-12i−1个元素。设当前位置为第i ii行第j jj列1 ≤ j ≤ 2 i − 1 1 \le j \le 2i-11≤j≤2i−1对应一维索引pos (i-1)^2 j。从第i ii行到第i 1 i1i1行的三种移动在一维索引上的偏移量分别为左下方j → j j \to jj→j即索引增加2 i − 1 2i-12i−1正下方j → j 1 j \to j1j→j1即索引增加2 i 2i2i右下方j → j 2 j \to j2j→j2即索引增加2 i 1 2i12i1。统一写作pos len q其中len 2i-1q 0, 1, 2分别对应左、正、右。关键观察经过n − 1 n-1n−1步后最终列索引与l − r l-rl−r存在确定关系。设最终位于第n nn行第p pp列则p n ( r − l ) n d p n (r - l) n dpn(r−l)nd其中d r − l d r - ldr−l。因此约束∣ l − r ∣ ≤ k |l-r| \le k∣l−r∣≤k等价于最终列索引满足n − k ≤ p ≤ n k n-k \le p \le nkn−k≤p≤nk。由于最终列索引唯一决定了d dd而中间步骤的d dd值不影响最终约束因此 DP 状态只需记录到达每个位置的最大和无需额外维度跟踪d dd。2. 算法实现输入与索引映射读入n , k n, kn,k将三角形所有n 2 n^2n2个整数按行优先顺序存入一维数组a[1..n*n]。DP 初始化创建一维数组dp[1..n*n]所有元素初始化为极小值NEG -4e18。起点dp[1] a[1]。逐行转移对于第i ii行i 1 ∼ n − 1 i 1 \sim n-1i1∼n−1令len 2i-1。遍历该行所有位置j从( i − 1 ) 2 1 (i-1)^21(i−1)21到i 2 i^2i2若dp[j]为NEG跳过不可达。对q 0, 1, 2计算下一行对应位置nj j len q更新dp[nj] max(dp[nj], dp[j] a[nj])统计答案最后一行索引范围从L (n-1)^21到L 2n - 2。中间位置mid L (n-1)对应第n nn列。合法列范围[ n − k , n k ] [n-k, nk][n−k,nk]对应索引范围[max(L, mid-k), min(L2n-2, midk)]。在该范围内取dp的最大值即为答案。3. 复杂度分析时间复杂度状态数为n 2 n^2n2每个状态转移O ( 1 ) O(1)O(1)3 个方向总复杂度O ( n 2 ) O(n^2)O(n2)。n ≤ 300 n \le 300n≤300运算量约2.7 × 10 5 2.7 \times 10^52.7×105非常快。空间复杂度需要一维数组a和dp大小均为O ( n 2 ) O(n^2)O(n2)约9 × 10 4 9 \times 10^49×104个long long空间消耗很小。总结利用一维索引统一表示三角形中的位置将三种移动转化为固定偏移量。通过分析最终列索引与l − r l-rl−r的线性关系将∣ l − r ∣ ≤ k |l-r| \le k∣l−r∣≤k的约束转化为对最后一行取值范围的限制从而只需一维 DP 即可求解。算法简洁高效完美处理n ≤ 300 n \le 300n≤300的数据规模。代码简要说明一维索引映射第i ii行第j jj列对应索引(i-1)^2 j下一行对应位置偏移len qlen 2i-1。DP 数组dp[pos]表示到达位置pos的最大路径和初始为极小值。转移过程对每行每个可达位置向下一行的三个方向尝试更新。答案范围最后一行中间位置mid (n-1)^2 n合法区间为[mid-k, midk]与最后一行边界的交集。注意使用long long防止大数溢出NEG取足够小的值如-4e18表示不可达。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cinnk;constll NEG-4e18;vectorlldp(n*n1,NEG);vectorlla(n*n1);for(ll i1;in*n;i){ll x;cinx;a[i]x;}dp[1]a[1];for(ll i1;in;i){ll len2*i-1;for(ll j(i-1)*(i-1)1;ji*i;j){for(ll q0;q3;q){dp[jqlen]max(dp[jqlen],dp[j]a[jqlen]);}}}ll ansNEG;ll L(n-1)*(n-1)1;ll midL(n-1);ll leftmax(L,mid-k);ll rightmin(L(2*n-2),midk);for(ll ileft;iright;i){ansmax(ans,dp[i]);}coutans;return0;}
延伸阅读

更多相关文章

2026/11/17 1:57:11

Hermes Agent 安装教程:Linux 下对接企业微信 AI Bot 的配置骨架

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/17 6:23:41

土·永恒记忆之载:集体记忆、交叉验证与遗忘权

土永恒记忆之载:集体记忆、交叉验证与遗忘权 一个分身的经验,全族的财富 第 14 篇讲了单个个体的十二层记忆;卷三篇三十九(第 141-145 条)把镜头拉远——当种群有多个分身时,记忆怎么变成"集体记忆&qu…

2026/11/17 20:33:45

自己能不能考电工证?考前押题帮你提高通过率

自己能不能考电工证?考前押题帮你提高通过率 怕考不过白交培训费?别慌,自己能不能考电工证其实早有明确政策,关键是你怎么准备。特别是像商丘这样的地级市,近年来对电工证报考门槛、考试流程和培训内容都做了规范,考前押题已经成为多数学员通过考试的重…

2026/11/17 20:33:45

天津高压电工证难考吗保姆级教程揭秘报名避坑指南

天津高压电工证难考吗保姆级教程揭秘报名避坑指南 你是不是也遇到过这样的情况:想找一个靠谱的地方报名高压电工证,结果被各种培训机构、中介搞得晕头转向,生怕花冤枉钱还拿不到证?别急,这篇文章就是为你量身打造的 天津高压电工证难考吗保姆级教程…

2026/11/17 20:33:45

收高压电工证多少钱怎么考

高压电工证多少钱怎么考?实操考试心里没底怕挂科?这份攻略帮你搞定 实操考试心里没底怕挂科?高压电工证含金量高不高?不少准备报考的人在心里打鼓,担心流程复杂、考试难度大、费用不透明。其实,只要掌握好报考流程、复习方法和考试技巧,高压电工证考试…

2026/11/17 20:33:45

办高压电工证报考条件行业前景与薪资待遇

高压电工证报考条件在哪考?证书过期了不知道怎么复审延期 证书过期了不知道怎么复审延期,这事儿可不能拖!尤其是像你这种河南劳务班组负责人,手里握着十几号人的施工队,高压电工证一过期,别说接活儿,连现场作业资格都没了。所以今天必须把【办高压电工…

2026/11/17 20:33:45

电工证复审政策最新官方回应:工地太忙没时间复习怎么办?

电工证复审政策最新官方回应:工地太忙没时间复习怎么办? 工地太忙根本没时间复习考试,你不是一个人。尤其是像我们信阳浉河区的水利工程从业者,天天在工地跑,手上的活儿忙得连轴转,哪还有空去准备电工证复审的考试?不过,别慌,官方回应已经出炉,…

2026/11/17 20:28:44

应县电工证在哪考取多久拿证 工地太忙怎么快速拿证

应县电工证在哪考取多久拿证 工地太忙怎么快速拿证 工地太忙根本没时间复习考试,你是不是也遇到过这种情况?每天忙得脚不沾地,还被催着要电工证,但一想到要考试,就感觉时间根本不够用。别急,应县电工证在哪考取,多久拿证,这些问题我们今天一次性说清…

2026/11/17 17:09:16

电工证考试口诉怎么准备值不值得考

电工证考试口诉怎么准备值不值得考 实操考试心里没底怕挂科,这是大多数准备考电工证的人心里最真实的感受。尤其是面对【电工证考试口诉】环节,很多人不知道该怎么准备,甚至担心自己说不好就被淘汰。其实,只要掌握方法, 值不值得考…

2026/11/16 5:30:20

桑植县考电工证千万别踩坑!报名全流程教你避坑

桑植县考电工证千万别踩坑!报名全流程教你避坑 你是不是也遇到过这种情况:想考个电工证,但不知道从哪儿下手,怕被中介坑,怕花冤枉钱,更怕考了证还不能用?别急,这正是你该看这篇文章的原因。在桑植县考电工证,确实有很多人被坑过,但只要你知道流程、…

2026/11/17 0:02:41

电工证操作和资格证有效期多久?真实经历告诉你怎么复审延期

电工证操作和资格证有效期多久?真实经历告诉你怎么复审延期 证书过期了不知道怎么复审延期,这种情况在电工圈里太常见了。我有个同事,去年刚把低压电工证给弄丢了,直到单位查岗才发现证书已经过期,差点被停工处理。今天就用我真实经历给你讲讲电工证操作…

2026/11/17 0:02:41

机修需不需要电工证 在哪考最靠谱 这些细节必须知道

机修需不需要电工证 在哪考最靠谱 这些细节必须知道 之前考的证在外省能不能转过来?这个问题几乎每个特种作业从业者都问过。特别是像你这样,之前在外省考了证,现在想在本地扎根,或者想换证、换岗的机修人员,最关心的就是【机修需不需要电工证】和【在…

2026/11/17 0:02:41

工地太忙根本没时间复习考试?真实经历告诉你电工证年检步骤是什么

工地太忙根本没时间复习考试?真实经历告诉你电工证年检步骤是什么 工地太忙根本没时间复习考试,我理解你。作为一名刚从焦作工程类院校毕业的学生,我也经历过这种困扰。电工证年检步骤是什么,听起来简单,但实际操作中,很多人因为流程不清楚、资料准备不…

2026/11/17 0:49:41

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/16 3:17:47

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑