大佬们想问一下携程笔试要多少分才算过啊
你来到了一个迷宫，迷宫共有 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
输出描述：
对于每组测试数据，输出一个整数，代表从小红总收益的最大值。
类似资料：