收集金币【牛客tracker 每日一题】

收集金币时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述现有一个n nn行m mm列的网格迷宫每个方格要么是可以通过的空方格要么是不可通过的墙方格迷宫的四周边界外都是墙方格。初始时迷宫中不存在墙方格。我们使用( i , j ) (i,j)(i,j)表示网格中从上往下数第i ii行和从左往右数第j jj列的方格里面有a i , j a_{i,j}ai,j​个金币。在开始移动前小K KK已经知道了t tt条信息每条信息以一个三元组{ x , y , v } \{x,y,v\}{x,y,v}表示代表( x , y ) (x,y)(x,y)方格会在第v vv回合永久变成墙方格在此之前金币仍可收集。每一回合开始时方格先发生变化小K KK再进行移动特别地如果起点在第一回合变为墙方格视作小K KK不受影响。小K从左上角( 1 , 1 ) (1,1)(1,1)方格出发记当前所在的位置为( x , y ) (x,y)(x,y)每回合只能向右移动一格到达( x , y 1 ) (x,y1)(x,y1)或向下移动一格到达( x 1 , y ) (x1,y)(x1,y)。每一个方格中的金币只能收集一次请问小K最多能收集到多少金币输入描述第一行输入两个整数n , m ( 1 ≦ n , m ≦ 1000 ) n,m(1≦n,m≦1000)n,m(1≦n,m≦1000)代表迷宫的大小。此后n nn行每行输入m mm个整数a i , 1 , a i , 2 , … , a i , m ( 1 ≦ a i , j ≦ 100 ) a_{i,1},a_{i,2},…,a_{i,m}(1≦a_{i,j}≦100)ai,1​,ai,2​,…,ai,m​(1≦ai,j​≦100)代表每个迷宫方格的金币数量。第n 2 n2n2行输入一个整数t ( 1 ≦ t ≦ n × m ) t(1≦t≦n×m)t(1≦t≦n×m)代表信息条数。此后t tt行每行输入三个整数x , y , v ( 1 ≦ x ≦ n ; 1 ≦ y ≦ m ; 1 ≦ v ≦ n × m ) x,y,v(1≦x≦n; 1≦y≦m; 1≦v≦n×m)x,y,v(1≦x≦n;1≦y≦m;1≦v≦n×m)代表一条信息。保证每一条信息的( x , y ) (x,y)(x,y)互不相同。输出描述输出一个整数代表小K KK最多能收集到的金币数量。示例1输入3 3 1 100 100 1 100 100 1 1 1 3 1 1 1 1 2 1 2 2 2输出5说明在这个样例中我们使用□ □□表示墙方格用∙ ∙∙表示小K当前回合所在的位置。初始时迷宫状态如公式所示[ ∙ 100 100 1 100 100 1 1 1 ] (0) \left[ \begin{matrix} ∙ 100 100\\ 1 100 100 \\ 1 1 1 \end{matrix} \right] \tag{0}​∙11​1001001​1001001​​(0)第一回合由于( 1 , 2 ) (1,2)(1,2)会在第一回合变为墙方格所以他只能走到( 2 , 1 ) (2,1)(2,1)第一回合结束时小K KK已经得到了2 22个金币迷宫状态如公式所示[ □ □ 100 ∙ 100 100 1 1 1 ] (1) \left[ \begin{matrix} □ □ 100\\ ∙ 100 100 \\ 1 1 1 \end{matrix} \right] \tag{1}​□∙1​□1001​1001001​​(1)第二回合小K只能向下移动到( 2 , 2 ) (2,2)(2,2)第二回合结束时小K已经得到了3 33个金币迷宫状态如公式所示[ □ □ 100 □ 100 ∙ 1 1 ] (2) \left[ \begin{matrix} □ □ 100\\ □ 100 \\ ∙ 1 1 \end{matrix} \right] \tag{2}​□∙​□□1​1001001​​(2)剩余的回合迷宫不再发生变化而由于小K KK只能向下或者右移动所以他至多收集到( 3 , 2 ) (3,2)(3,2)和( 3 , 3 ) (3,3)(3,3)两个方格的金币。加起来刚好是5 55个金币。示例2输入3 3 1 100 100 100 100 100 100 100 100 2 2 1 1 1 2 1输出1解题思路本题核心是动态规划结合移动步数限制求解最大金币收集数。小K KK仅能向右、向下移动到达格子( i , j ) (i,j)(i,j)的回合数为i j − 2 ij-2ij−2该数值必须小于格子变墙的回合数才能进入该格子收集金币。定义d p [ i ] [ j ] dp[i][j]dp[i][j]表示到达( i , j ) (i,j)(i,j)能收集的最大金币数量初始化起点d p [ 1 ] [ 1 ] dp[1][1]dp[1][1]为起点金币数其余位置标记为不可达。遍历整个网格仅在满足步数限制时从上方或左方合法位置转移状态累加当前格子金币并更新最大值。全程维护全局最大金币数最终即为答案时间复杂度O ( n m ) O(nm)O(nm)完美适配n , m ≤ 1000 n,m≤1000n,m≤1000的数据规模。总结核心逻辑动态规划记录路径最大金币通过到达回合数 变墙回合数判断格子合法性。关键操作仅从左、上两个方向转移状态遍历过程中实时更新最大金币值。效率保障二维网格线性遍历无冗余计算高效处理题目所有限制条件。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M5e310;ll a[N][N],t[N][N],f[N][N],ans;intmain(){ll n,m;cinnm;for(ll i1;in;i)for(ll j1;jm;j)cina[i][j],t[i][j]INT_MAX;for(ll i0;in;i)for(ll j0;jm;j)f[i][j]-1;ll T;cinT;while(T--){ll x,y,v;cinxyv;t[x][y]v;}f[1][1]a[1][1];for(ll i1;in;i)for(ll j1;jm;j){if(i-1j-1t[i][j]){if(f[i-1][j]!-1)f[i][j]max(f[i][j],f[i-1][j]a[i][j]);if(f[i][j-1]!-1)f[i][j]max(f[i][j],f[i][j-1]a[i][j]);ansmax(ans,f[i][j]);}}coutansendl;return0;}