作者thumbg75446 (EDWIN)
看板Programming
标题[问题] 分割阵列问题请教
时间Fri Mar 1 13:20:57 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/Programming/M.1709270459.A.7DA.html
1F：推 gusion: 这个问题的分割方式，简化来看，就是在两 27.240.186.220 03/01 14:07
2F：→ gusion: 个负数之间的逗号位置选一个切一刀，或者 27.240.186.220 03/01 14:07
3F：→ gusion: 不选，所以范例中的-2和-5之间有三个逗号 27.240.186.220 03/01 14:07
4F：→ gusion: 位置可以分割，也可以不选，因此共(3+1)种 27.240.186.220 03/01 14:07
5F：→ gusion: 计算逗号数的方式就两个index相减就好 27.240.186.220 03/01 14:07
6F：→ gusion: 如果array中有很多负数也是同理，只要把两 27.240.186.220 03/01 14:07
7F：→ gusion: 个负数间可以切的方式数量乘起来就好 27.240.186.220 03/01 14:07
8F：→ gusion: 例如：1, -2, 3, 4, -5, -6, 7, -8, 9 27.240.186.220 03/01 14:07
9F：→ gusion: 共 (3+1)*(1+1)*(2+1) 种分割方式 27.240.186.220 03/01 14:07
10F：→ gusion: 写成code就是直接array扫一遍，扫到负数时 27.240.186.220 03/01 14:07
11F：→ gusion: ，看跟前一个负数差多少index，加一後乘在 27.240.186.220 03/01 14:07
12F：→ gusion: result变数应该就可 27.240.186.220 03/01 14:07
13F：→ thumbg75446: 谢谢回答 但是是否遇到连续负数的arr 42.70.171.68 03/01 14:23
14F：→ thumbg75446: ay就没办法了呢？比如说[-1,-1,-1,-1 42.70.171.68 03/01 14:23
15F：→ thumbg75446: ,3] 42.70.171.68 03/01 14:23
16F：推 gusion: 连续负数也可以啊，上面推文例子的-5和-6 27.240.186.220 03/01 14:48
17F：→ gusion: 就是，两个index差1，中间可以切一刀，或 27.240.186.220 03/01 14:48
18F：→ gusion: 者不切，所以就是(1+1)，然後跟其他段的数 27.240.186.220 03/01 14:48
19F：→ gusion: 量乘起来就好 27.240.186.220 03/01 14:48
20F：→ gusion: 你的例子就是(1+1)*(1+1)*(1+1)，共8种 27.240.186.220 03/01 14:50
21F：→ thumbg75446: 谢谢回覆 理解了 42.70.171.68 03/01 17:42