tiktok ng oa

匿名用户 发表于 2022-11-15 16:31
好的 谢谢老哥！

这个用dp会超时过不了，换成挨个试x和y的值能过, z = n - x - y, 10x+30y+50z = m

匿名用户 发表于 2022-11-15 08:26:07
coding第一题是用动态规划吗 还是回溯
（好吧典型背包问题）

这题能O(1).jpg

nango94213 发表于 2022-11-15 20:47:40
这个用dp会超时过不了，换成挨个试x和y的值能过, z = n - x - y, 10x+30y+50z = m

妙！谢谢老哥！

可以问下完选择题嘛

微信用户_er5al 发表于 2022-11-16 12:33
可以问下完选择题嘛

同求 谢谢大佬们 ！！

看到另一个大佬发了选择题！！
原文链接：https://www.1point3acres.com/bbs/thread-946310-1-1.html

giftcard背包问题变形

浅谈一下我的思路：
1. gitcard不是背包问题，解方程组就可以，时间复杂度o(n)
2. dust 问题用map合并区间，使用lower_bound函数，时间复杂度o(nlogn)
3. dijkstra寻找最小路径。找不到路径就返回0 （不知道为啥题目中没写此时需要返回啥，我试了很多值只有0过了test :( sb题目）

小亩_bcbacdf 发表于 2022-11-16 16:25
浅谈一下我的思路：
1. gitcard不是背包问题，解方程组就可以，时间复杂度o(n)
2. dust 问题用map合并区 ...

倒也不是返回0才行。是你返回0刚好碰上了它的testcase

gift card 用三维dp: