携程笔试5.6

前两道a了 第三天最大公约数不知道是啥，测试通过，提交就是不对0最后一道0无了

1、给定一个N，打印一个序列，如N=5，输出55555 55555555552、给定一个栈，初始时栈中为空。有m次操作，每次操作向栈口压入一个数字。在一次操作之后，如果栈中有两个连续的相同数字x，则它们会合并成数字x+1。如果仍有，则重复此过程(可以证明同一时刻最多只有一组两个连续的相同数字)。问m次操作之后栈中的数字自底向上是多少?3、给出一个长度为n的数组a1;42，…,an,假如你从2点出发(初始区间为[,æ],初始价值为a)，每到达一个点就把这个点加入到区间内并获得当前点的价值，每次能将当前所拥有的区间向右或者向左扩展一个(不能超过边界),且被拓展的位置的值一定要大于当前所拥有的价值...

刚刚笔试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输出描述：对于每组测试数据，输出一个整数，代表从小红总收益的最大值。

1，1，1，0.3，这得抬我进面了吧 #携程#