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