科大讯飞笔试第三题

第三题是根据条件可知最长合并的情况是1，2， 4， 8， 16，...，2^30，说明区间长度最大不会超过30，直接对每个位置dfs加记忆化搜索 int m[1e5][30]; int ps[1e5]; // 前缀和 int n; int arr[1e5]; int dfs(l, size) { if(m[i][size]!=-1)return m[i][size]; int r = i+size-1; int sum = ps[r+1]-ps[l]; int ans=sum; if(r+1<n &amp;&amp; sum < arr[r+1]){ ans = dfs(l, size+1); } if(l-1>=0 &amp;&amp; sum < arr[l-1]){ ans = max(ans, dfs(l-1, size+1)); } m[l][size] = ans; return ans; }

同20，问题在于没考虑到左右相等情况，我举个例子12 12 1 12 30，这里1左右都一样，但是选左边就不对，看别人说要用dfs

递归深搜每一位，规定左右边界，满足条件向下递归，dp进去维护每一位最大值，这也不算动态规划，就模拟就好了

这样的话思路不对，比如100000 3 1 2这个例子从1开始扩展就会出错。因为我开始这是这么做的😂。我用dfs做的过了，就是每一步有向右扩展，向左扩展两种选择，直到无法扩展就停止记录下来此时的sum到一个list里面，然后找到list里面的最大值就可以了，本来以为会超时结果过了，神奇

dfs爆搜😸

第三题dfs过了，第二题暴力只过了11%，然后改成维护数量后排序过了5％，感觉把排序改成堆可以多过一些，可惜最后没时间了，时间全浪费在最后一题了。。。

多少分过啊

回溯 或者 dfs每次搜索左右就好了

思路不对，比如5 3 1 2