[請問] 程式問題請教

看板ask作者 (EDWIN)時間2月前 (2024/03/01 09:01), 編輯推噓0(0推 0噓 13→)
留言13則, 2人參與, 2月前最新討論串1/1
請教一個問題，給定一個整型數組，值有正有負，需要把整個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://www.ptt.cc/bbs/ask/M.1709254879.A.E39.html
→
03/01 09:19, 2月前 , 1F
每個 sub array 都至少要有一個負數，所以先把非負數
03/01 09:19, 1F
→
03/01 09:20, 2月前 , 2F
去除，然後想像剩餘負數之間有幾個可以插入分隔線的空位
03/01 09:20, 2F
→
03/01 09:21, 2月前 , 3F
先窮舉出分隔線有幾種插入法。以你舉的例子，分隔線只會
03/01 09:21, 3F
→
03/01 09:21, 2月前 , 4F
有一條而且必須插在-2和-5之間。
03/01 09:21, 4F
→
03/01 09:22, 2月前 , 5F
啊我忘了還可以完全不插 XD
03/01 09:22, 5F
→
03/01 09:23, 2月前 , 6F
下一步再回頭考慮有非負數的狀況，-2和-5之間還有3和4
03/01 09:23, 6F
→
03/01 09:24, 2月前 , 7F
那麼唯一的分隔線有三個位置可以選擇
03/01 09:24, 7F
→
03/01 09:25, 2月前 , 8F
要不要用recursive要不要用dynamic programming都是其次
03/01 09:25, 8F
→
03/01 09:26, 2月前 , 9F
先把演算過程做對比較重要
03/01 09:26, 9F
→
03/01 09:27, 2月前 , 10F
程式類問題可以去相關語言討論板如 C_and_CPP、Python
03/01 09:27, 10F
→
03/01 09:27, 2月前 , 11F
不分語言的討論也可以去Programming
03/01 09:27, 11F
→
03/01 09:28, 2月前 , 12F
這些板看起來冷門，但只要有新文章就會有人去看的
03/01 09:28, 12F
→
03/01 13:17, 2月前 , 13F
謝謝我去那邊問問看
03/01 13:17, 13F
‣ 更多 thumbg75446 的文章
文章代碼(AID): #1buIZVuv (ask)