腾讯2020-8-23 20点场讨论区

各位是不是被今天的题难倒了？ 交卷后（十点后）欢迎各位分享题解。我是开发岗， 题目如下。

骗分真的好。 这次T5骗不了分。
我说一下我的渣题解吧。

T1. 直接模拟链表。

T2. 我用的暴力， 因为K最大为5， 我把所有长度小于等于5的字符串放在vector里面， 用hash判重， 然后排序就可以了。

T3. 数学题。 考虑进位， 每有一个进位， 则数字和 + 9， 问题转化为至多进位的个数。

从后往前扫一遍， 如果是9或者前面已经没有数字了就不能进位， 否则就进位。 注意进位要先减再判断。 比如108这个数可以进位两次而109只有一次。

T4. dp. 
设f(x,y)为填满前x列， 最后一列用第y种方法填满时的最小消耗。
这里定义y == 0是横向， y == 1是纵向。

纵向的时候很好转移， 因为只需要涂满这一列。 所以 f(x, 1) = min(f(x-1, 0), f(x-1, 1)) + 1.

横向的时候有个问题， 就是因为前面横向的会影响到后面。 所以我们得考虑前面若干个都是横向的， 判断这一列涂了几个才能计算。

所以考虑其中 第i个是最后一个纵向涂的那么剩下的都是横向涂， 已涂的高度是h' = min(h[i + 1], h[i + 2], ..., h[x - 1]. 若h' > h[x], 则不用涂， 否则要涂剩余部分。所以得到以下式子
f(x, 0) = min{f(i, 1) + max(0, h[i] - min(h[i + 1], h[i + 2],..., h[x - 1])) }

因此最终答案ans = min(f(n, 0), f(n, 1)).

然而这道题输出n有55pts.

最后一题我只会暴力的dp， 貌似lc上面有。

最终得分
1 1 1 1 1