作者thumbg75446 (EDWIN)
看板ask
标题[请问] 程式问题请教
时间Fri Mar 1 09:01:17 2024
请教一个问题，给定一个整型数组，值有正有负，需要把整个arr分割成若干个subarr，
但必须满足每个subarr都至少包含一个负数，请问有几种分割数？例如[1,-2,3,4,-5]只
有以下分割方式
[1,-2|3,4,-5]
[1,-2,3|4,-5]
[1,-2,3,4|-5]
[1,-2,3,4,-5]
想问一下具体的思路是什麽？有人说是dp+recursive但我看不太出来..
或是有专版可以询问吗谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.70.171.68 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/ask/M.1709254879.A.E39.html
1F：→ Schottky: 每个 sub array 都至少要有一个负数，所以先把非负数 03/01 09:19
2F：→ Schottky: 去除，然後想像剩余负数之间有几个可以插入分隔线的空位 03/01 09:20
3F：→ Schottky: 先穷举出分隔线有几种插入法。以你举的例子，分隔线只会 03/01 09:21
4F：→ Schottky: 有一条而且必须插在-2和-5之间。 03/01 09:21
5F：→ Schottky: 啊我忘了还可以完全不插 XD 03/01 09:22
6F：→ Schottky: 下一步再回头考虑有非负数的状况，-2和-5之间还有3和4 03/01 09:23
7F：→ Schottky: 那麽唯一的分隔线有三个位置可以选择 03/01 09:24
8F：→ Schottky: 要不要用recursive要不要用dynamic programming都是其次 03/01 09:25
9F：→ Schottky: 先把演算过程做对比较重要 03/01 09:26
10F：→ Schottky: 程式类问题可以去相关语言讨论板如 C_and_CPP、Python 03/01 09:27
11F：→ Schottky: 不分语言的讨论也可以去Programming 03/01 09:27
12F：→ Schottky: 这些板看起来冷门，但只要有新文章就会有人去看的 03/01 09:28
13F：→ thumbg75446: 谢谢我去那边问问看 03/01 13:17
14F：推 yzfr6: 阵列 03/04 21:34