2023-08-26 17:00 南京外国语学校算法工程师发布于江苏

关注

C. Kevin的七彩旗 without dp

Kevin的七彩旗

https://ac.nowcoder.com/acm/contest/63804/C

看到官方解法是 DP 于是回来补个档，我没用 DP，看不懂 DP 的可以看看这个题解。

提示 1：分段一定是分成若干个 $\{i,i 1,i 2,i 3,\dots\}$ 的序列。

提示 2：我们发现拼接数列的时候，如果两个数列元素有重叠不影响可行性；如果不是完全包含也不影响最优性。

所以我们直接找出，对于每个元素，它能直接连到后面的最大元素。我们设为 $f(i)$ ，那么拿样例来举例子， $[2,1,4,5,6,7,3,4,1,2]\to[2][1][4,5,6,7][3,4][1,2]$ ， $f=\{2,2,4,7,7,7,7\}$ 。

注意到，虽然在 $[1]$ 这一段中 $1$ 只能到 $1$ ，但是它在 $[1,2]$ 中可以到 $2$ ，所以 $f(1)=2$ 。

我们考虑对 $x$ 初值为 $1$ ，不断进行 $x\gets f(x) 1$ 的迭代，迭代次数就是答案，如果迭代永远无法到达 $m$ 就是 $-1$ 。

Code

全部评论

推荐最新楼层

zhangas

山东科技大学 C++

很巧的方法，感谢分享

点赞回复分享

发布于 2023-08-26 18:44 山东

昨天 18:35

Momenta_算法

Momenta 11月还有hc的岗位

11月还没投的看看这几个岗位吧 目前还有些hc，其他岗位在泡池子or发offer了已经重要岗位提示：端到端算法工程师深度学习算法工程师感知算法工程师决策规划算法工程师前端开发工程师系统架构与集成工程师（德语）系统架构与集成工程师（日语）offer就和抢演唱会票一样，抢完第一波之后等回流了，大佬拿着再多意向书，最后也只能签一个，，越厉害的，拿的offer越多，且都是非线性增长的，只要上面的人释放完意向，紧接着链式反应，大家都会有有offer的，其实最难的不是offer，而是进入了公司，发现累的要死，很多同学进入了工作后，朋友圈就没有更新过了，所以大家在签约的时候一定要打听清楚！ 目前的重点还...

投递Momenta等公司10个岗位 >

点赞评论收藏

昨天 18:31

360集团_算法

360还能入股吗？

大家千万别嫌找工作麻烦，说实话找了一个糟心的工作，更麻烦，那种每天的过的很压抑的感觉，真的只能辞职了，就和我学弟当初一样，你会发现投简历时偷的懒，等入职之后再办理辞职手续会双倍打回来，我建议至少有四个比较满意的offer了再水，现在多投投，多点选择！公司有免费的三餐，饭量大的可能吃不饱，有健身房，器械不多。但是我喜欢这里的篮球厂，还有台球和乒乓球可以玩。周末来玩玩，再吃点公司得饭挺香的，哈哈哈哈。电梯的话，每天早上要等的比较久，我在6层懒得排队，直接楼梯上去。每天9.30工作到11.30，午休单2点，然后6.30下班，时间不久。新人有12天年假，每个月还有1天不用病假条的病假（累计一年24天假...

投递360集团等公司10个岗位 >

点赞评论收藏

10-09 10:06

蚌埠坦克学院算法工程师

闺蜜公司

一人来一句闺蜜牛逼

尊尼获获：闺蜜在哪？

点赞评论收藏

11-21 11:39

四川大学 Java

结束一切

明年七月份去上班，爽玩大半年了

是红鸢啊：忘了还没结束，还有字节的5k 违约金

点赞评论收藏

不愿透露姓名的神秘牛友

11-28 23:31

网易工作体验（已离职）

首先，工位环境嘛，工位桌子小，差不多1.6米宽，配一台电脑。午休能不能躺下就看你领导的风格了。工作时间基本上是9:30前打卡，中午12点到1:30吃饭，下午1:30到6:30。薪资和福利方面，岗位差别大，平均水平还行。五险一金和商业保险都挺良心，女性怀孕期间工资照发，还有生育补贴。最重要的是，网易的饭堂真的很好吃，还有健身房、瑜伽课和咖啡吧。工作强度嘛，主要看你自己的能力和领导的需求。项目的紧急程度、领导的风格、团队的氛围都会影响到你。

网易公司福利 162人发布

点赞评论收藏

全站热榜

正在热议

# 工作中，你有没有遇到非常爱骂人的领导？ #

# 如果再来一次，你还会选择这个工作吗？ #

110956次浏览 1116人参与

# 25届机械人为了秋招做了哪些准备？ #

25168次浏览 356人参与

# 签了三方后想毁约怎么办 #

18573次浏览 111人参与

# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #

# 实习想申请秋招offer，能不能argue薪资 #

35804次浏览 308人参与