企业官网建设流程全解析

三角形取数(Hard Version)

时间限制：1 秒
空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定一个由n nn行构成的数字三角形。第i ii行共有2 i − 1 2i - 12i−1个整数，整体形状如下图所示（以n = 3 n = 3n=3为例）：

1 2 3 4 5 6 7 8 9

从顶点（第一行唯一的数字）出发，依次向下移动恰好n − 1 n - 1n−1次直到抵达最后一行。

假设当前位于第i ii行第j jj列：

1. 可以向正下方移动至第( i + 1 ) (i + 1)(i+1)行第j jj列；
2. 可以向左下方移动至第( i + 1 ) (i + 1)(i+1)行第( j − 1 ) (j - 1)(j−1)列；
3. 可以向右下方移动至第( i + 1 ) (i + 1)(i+1)行第( j + 1 ) (j + 1)(j+1)列。

每到达一个位置都会获得该位置的数值。定义在整个行走过程中，向左下方移动的次数记为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_{i=1}^{n} (2i - 1) = n^2i=1∑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 = 131+4+8=13，且∣ 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≤300
• 0 ≤ 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−r=d时能获得的最大数值之和（d dd加上偏移量n nn以避免负数下标）。转移时由上一行的( j − 1 ) (j-1)(j−1)、j jj、( j + 1 ) (j+1)(j+1)三个位置推来，并相应地让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)^2+1(i−1)2+1到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 i+1i+1行的三种移动，在一维索引上的偏移量分别为：
  • 左下方：j → j j \to jj→j，即索引增加2 i − 1 2i-12i−1；
  • 正下方：j → j + 1 j \to j+1j→j+1，即索引增加2 i 2i2i；
  • 右下方：j → j + 2 j \to j+2j→j+2，即索引增加2 i + 1 2i+12i+1。
    统一写作pos + len + q，其中len = 2i-1，q = 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 + dp=n+(r−l)=n+d
  其中d = r − l d = r - ld=r−l。因此约束∣ l − r ∣ ≤ k |l-r| \le k∣l−r∣≤k等价于最终列索引满足n − k ≤ p ≤ n + k n-k \le p \le n+kn−k≤p≤n+k。
• 由于最终列索引唯一决定了d dd，而中间步骤的d dd值不影响最终约束，因此 DP 状态只需记录到达每个位置的最大和，无需额外维度跟踪d dd。

2. 算法实现

1. 输入与索引映射：读入n , k n, kn,k，将三角形所有n 2 n^2n2个整数按行优先顺序存入一维数组a[1..n*n]。
2. DP 初始化：创建一维数组dp[1..n*n]，所有元素初始化为极小值NEG = -4e18。起点dp[1] = a[1]。
3. 逐行转移：对于第i ii行（i = 1 ∼ n − 1 i = 1 \sim n-1i=1∼n−1），令len = 2i-1。遍历该行所有位置j（从( i − 1 ) 2 + 1 (i-1)^2+1(i−1)2+1到i 2 i^2i2）：
   • 若dp[j]为NEG，跳过（不可达）。
   • 对q = 0, 1, 2，计算下一行对应位置nj = j + len + q，更新：

     dp[nj] = max(dp[nj], dp[j] + a[nj])

4. 统计答案：最后一行索引范围从L = (n-1)^2+1到L + 2n - 2。中间位置mid = L + (n-1)对应第n nn列。合法列范围[ n − k , n + k ] [n-k, n+k][n−k,n+k]对应索引范围[max(L, mid-k), min(L+2n-2, mid+k)]。在该范围内取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 + q（len = 2i-1）。
• DP 数组：dp[pos]表示到达位置pos的最大路径和，初始为极小值。
• 转移过程：对每行每个可达位置，向下一行的三个方向尝试更新。
• 答案范围：最后一行中间位置mid = (n-1)^2 + n，合法区间为[mid-k, mid+k]与最后一行边界的交集。
• 注意：使用long long防止大数溢出，NEG取足够小的值（如-4e18）表示不可达。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cin>>n>>k;constll NEG=-4e18;vector<ll>dp(n*n+1,NEG);vector<ll>a(n*n+1);for(ll i=1;i<=n*n;i++){ll x;cin>>x;a[i]=x;}dp[1]=a[1];for(ll i=1;i<n;i++){ll len=2*i-1;for(ll j=(i-1)*(i-1)+1;j<=i*i;j++){for(ll q=0;q<3;q++){dp[j+q+len]=max(dp[j+q+len],dp[j]+a[j+q+len]);}}}ll ans=NEG;ll L=(n-1)*(n-1)+1;ll mid=L+(n-1);ll left=max(L,mid-k);ll right=min(L+(2*n-2),mid+k);for(ll i=left;i<=right;i++){ans=max(ans,dp[i]);}cout<<ans;return0;}