作者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/m.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