P1107 雷涛的小猫【洛谷算法习题】

P1107 雷涛的小猫网页链接P1107 雷涛的小猫题目背景原最大整数参见 P1012题目描述雷涛同学非常的有爱心在他的宿舍里养着一只因为受伤被救助的小猫当然这样的行为是违反学生宿舍管理条例的。在他的照顾下小猫很快恢复了健康并且愈发的活泼可爱了。可是有一天雷涛下课回到寝室却发现小猫不见了经过一番寻找才发现她正趴在阳台上对窗外的柿子树发呆…在北京大学的校园里有许多柿子树在雷涛所在的宿舍楼前就有N NN棵。并且这N NN棵柿子树每棵的高度都是H HH。冬天的寒冷渐渐笼罩了大地树上的叶子渐渐掉光了只剩下一个个黄澄澄的柿子看着非常喜人。而雷涛的小猫恰好非常的爱吃柿子看着窗外树上的柿子她十分眼馋于是决定利用自己敏捷的跳跃能力跳到树上去吃柿子。小猫可以从宿舍的阳台上跳到窗外任意一棵柿子树的树顶。之后她每次都可以在当前位置沿着当前所在的柿子树向下跳1 11单位距离。当然小猫的能力远不止如此她还可以在树之间跳跃。每次她都可以从当前这棵树跳到另外的任意一棵在这个过程中她的高度会下降Delta单位距离。每个时刻只要她所在的位置有柿子她就可以吃掉。整个“吃柿子行动”一直到小猫落到地面上为止。雷涛调查了所有柿子树上柿子的生长情况。他很想知道小猫从阳台出发最多能吃到多少柿子他知道写一个程序可以很容易的解决这个问题但是他现在懒于写任何代码。于是现在你的任务就是帮助雷涛写一个这样的程序。图为N 3 , H 10 , D e l t a 2 N3, H10, Delta2N3,H10,Delta2的一个例子。小猫按照图示路线进行跳跃可以吃到最多的8 88个柿子。输入格式第一行有三个以空格分隔的整数分别代表N , H , D e l t a N,H,DeltaN,H,Delta。接下来的N NN行每行第一个整数为N i N_iNi​代表第i ii棵树上的柿子数量。接下来是N i N_iNi​个整数每个整数T i , j T_{i,j}Ti,j​代表第i ii棵柿子树的T i , j T_{i,j}Ti,j​高度上长有一个柿子。输出格式一个整数即小猫最多吃到的柿子数。输入输出样例 #1输入 #13 10 2 3 1 4 10 6 3 5 9 7 8 9 5 4 5 3 6 9输出 #18说明/提示数据范围及约定对于全部数据1 ≤ N , H ≤ 2000 1 \leq N, H ≤ 20001≤N,H≤20000 ≤ N i ≤ 5000 0 \leq N_i ≤ 50000≤Ni​≤50001 ≤ D e l t a ≤ H , 1 ≤ T i , j ≤ H 1 ≤ Delta ≤ H,1 ≤ T_{i,j} ≤ H1≤Delta≤H,1≤Ti,j​≤H。输入文件大小不大于 40MB。注意输入输出效率。来源 Excalibur, 2008。解题思路本题核心是动态规划全局最大值优化求解小猫吃柿子的最大数量适配两种跳跃规则。定义dp[i][j]为在第i棵树、高度j能吃到的最大柿子数a[i][j]记录对应位置的柿子数量。从树顶向地面逆序遍历高度状态转移包含两种同树向下跳1单位、跨树跳下降Delta单位。用pre数组维护每个高度的全局最大dp值将跨树转移的复杂度从O(N)优化为O(1)。遍历所有状态后取最大值即为答案整体时间复杂度O(N×H)完美适配N、H≤2000的数据规模。总结核心逻辑动态规划处理同树下落、跨树跳跃两种行为利用全局最大值数组优化状态转移。关键操作逆序高度递推DP值pre数组记录各高度最优解实时更新全局最大柿子数。效率保障O(N×H)线性复杂度消除冗余遍历高效处理题目数据与输入规模限制。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N5e310;constll p1e97;constll INF1e18;constll M2e310;ll a[N][M],dp[N][M],pre[N];intmain(){ll n,h,de;cinnhde;for(ll i1;in;i){ll t,y;cint;while(t--){ciny;a[i][y];}}ll mx0;for(ll jh;j0;j--){for(ll i1;in;i){dp[i][j]a[i][j]dp[i][j1];//先继承上一次dp[i][j]max(dp[i][j],pre[jde]a[i][j]);//转移pre[j]max(pre[j],dp[i][j]);//尝试更新当前的premxmax(mx,dp[i][j]);}}coutmxendl;return0;}