首页 > 腾讯2020-8-23 20点场讨论区
头像
haozheyan97
编辑于 2020-08-23 22:36
+ 关注

腾讯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

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐