大佬,第二题的状态转移好像是一样的?
点赞 评论

相关推荐

刚刚笔试4道题只过了两道半,感觉悬了,第二题dp死活只有50%准确率,用dfs又超时了,当时一紧张完全忘了还能加memoization,唉,就是下面这道题,第二题挣扎了1个多小时导致第四题一点没碰,最后交卷前看了一眼好像不太难,亏死了你来到了一个迷宫,迷宫共有 n 关,每关有左侧和右侧两个宝箱,左侧宝箱的收益为 a_i,右侧宝箱的收益为 c_i。在每次只可以选择一个宝箱,然后到达下一关。当你在选择宝箱时,如果和上一关选择宝箱的方位相同则无损失。如果上一关选择了左侧宝箱,而这一关想要切换到右侧宝箱,那么需要支付 b_i 代价;如果上一关选择了右侧宝箱,而这一关想要切换到左侧宝箱,那么需要支付 d_i 代价(必须在进入下一关之前切换)。有些宝箱的收益和切换代价可能是负数!可以理解为,代价为负值相当于收益。你想知道,当通过 n 关后,总收益的最大值是多少?输入描述:本题为多组测试数据,第一行输入一个正整数 T(1 ≤ T ≤ 100),代表测试数据组数。对于每组测试数据,第一行输入一个正整数 n(1 ≤ n ≤ 1000),代表关卡数量。接下来有 n 行,每行四个整数 a_i, b_i, c_i, d_i(-100 ≤ a_i, b_i, c_i, d_i ≤ 100),具体代表题意中所述的数值。这道题dp怎么做,java输出描述:对于每组测试数据,输出一个整数,代表从小红总收益的最大值。
投递携程等公司10个岗位
点赞 评论 收藏
分享
牛客网
牛客企业服务