tt2022最后一波ng oa

nathanx · 2022-12-30 07:45:41

jeje想转码发表于 2022-12-28 14:42
Find the shortest subsequence of array that can be divided by K
请问是找sum能被K整除的最短连续subse ...

请问你最后找到题号了吗？

nathanx · 2022-12-30 07:54:09

楼主想问下最后一道题要求返回什么啊？是subarray最小的sum吗？

匿名用户-7B6G2 *2022-12-30 07:56:01* · 2022-12-30 07:56:01

匿名用户发表于 2022-12-29 18:03
请问大家有第三题的思路吗？或者类似的题型share一下谢谢🙏

同问！！！！！！！！！

来自APP · 2022-12-30 08:18:14

nathanx 发表于 2022-12-29 15:45:41
请问你最后找到题号了吗？

在overstackflow找到有length no greater than k的类似的题目用的是dp 不过不知道这个题用dp怎么做

jitbanerjee4 · 2022-12-30 09:30:07

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

soyokaze · 2022-12-30 09:37:09

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-7B6G2 *2022-12-30 09:43:06* · 2022-12-30 09:43:06

soyokaze 发表于 2022-12-29 20:37
greedy不行
M = 10 nums = [1, 5, 5, 1]
greedy: [[1, 5], [5, 1]], sum_max = 10

是的，感觉dp不是很简单，还不知道该怎么做

soyokaze · 2022-12-30 09:56:55

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

soyokaze · 2022-12-30 09:59:26

meme_mimi 发表于 2022-12-29 00:26:27
第三题"minimize the sum of maximum value from each division. " 是不是就是最小化subarrays 的数量？

不一定，看我前面提到那个1551的反例

来自APP · 2022-12-30 10:58:43

jitbanerjee4 发表于 2022-12-29 17:30:07
It seems it is impossible to use dp in both the 1st and 3rd problem.

第一题用prefix sum可以做吧