三角形取数(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;}