同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？
同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？
二分搜+單調隊列+greedy
或是二分搜內DP
同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？
二分搜+單調隊列+greedy
或是二分搜內DP
不對 應該不用單調隊列
linlincaleb@gmail.com
(臨末之頌)
學校
:
新北市立板橋高級中學
編號 : 132772
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？
二分搜+單調隊列+greedy
或是二分搜內DP
不對 應該不用單調隊列
其實只要把海報高度存到vector 之後sort
每次二分搜的時候看看每一段有多長 把它們記錄下來，之後DP
同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？
可以思考這個問題和 Subset Sum 問題、Bin Packing 問題的關聯性
這個延伸題應該是很有難度的
如果可以很快解這個延伸題，就可以很快的解 Subset Sum, Bin Packing
同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？
抱歉，當時我有想到一個greedy+二分搜做法，但後來討論後發現有特例，所以其實我也不知道有沒有快速的解（也許n要小一點），不過我覺得單調隊列有機會nlognlogC（logc指的是高度的二分搜），如果可以，這是可通過的解。
同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？
抱歉，當時我有想到一個greedy+二分搜做法，但後來討論後發現有特例，所以其實我也不知道有沒有快速的解（也許n要小一點），不過我覺得單調隊列有機會nlognlogC（logc指的是高度的二分搜），如果可以，這是可通過的解。
讓我想到這題：a455: TOI2010 第四題：商品特賣問題
每張海報長度可以視為需要被裝入箱中的物品重量，而每段連續的區間長度就是給定的ｎ種大小的箱子，雖然是最大化裝入箱的物品重量，但因為 M ≤ 50且 N ≤ 1000，morris1028 公開的方法是 IDDFS，對應回原題的限制範圍更大，但原 PO 的方法可以丟過來試試。
讓我想到這題：a455: TOI2010 第四題：商品特賣問題
每張海報長度可以視為需要被裝入箱中的物品重量，而每段連續的區間長度就是給定的ｎ種大小的箱子，雖然是最大化裝入箱的物品重量，但因為 M ≤ 50且 N ≤ 1000，morris1028 公開的方法是 IDDFS，對應回原題的限制範圍更大，但原 PO 的方法可以丟過來試試。
我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。
我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。
瑞1奇電電電orz
linlincaleb@gmail.com
(臨末之頌)
學校
:
新北市立板橋高級中學
編號 : 132772
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。
瑞1奇電電電orz
老鼠電電電orz
lai.abc8660@gmail.com
(alan lai)
學校
:
臺北市立成功高級中學
編號 : 81120
來源 : [128.6.147.3]
最後登入時間 ：
2025-09-12 08:02:28
我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。
瑞1奇電電電orz老鼠電電電orz
linlinmorz