發表新討論
#28889: 延伸題


r1cky (hehe)

學校 : 國立臺灣師範大學
編號 : 158637
來源 : [118.166.194.111]
最後登入時間 ：
2024-04-13 22:10:59
h084. 4. 牆上海報 -- 2022年1月APCS | From: [49.216.164.12] | 發表日期 : 2022-01-10 12:28

同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？

 
#28890: Re:延伸題


pcshic (PCSHIC)

學校 : 新北市立板橋高級中學
編號 : 4688
來源 : [140.112.16.183]
最後登入時間 ：
2024-04-13 16:28:28
h084. 4. 牆上海報 -- 2022年1月APCS | From: [203.64.161.154] | 發表日期 : 2022-01-10 12:29

同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？

二分搜+單調隊列+greedy

或是二分搜內DP

 
#28891: Re:延伸題


pcshic (PCSHIC)

學校 : 新北市立板橋高級中學
編號 : 4688
來源 : [140.112.16.183]
最後登入時間 ：
2024-04-13 16:28:28
h084. 4. 牆上海報 -- 2022年1月APCS | From: [203.64.161.154] | 發表日期 : 2022-01-10 12:30

同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？

二分搜+單調隊列+greedy

或是二分搜內DP

不對 應該不用單調隊列 

 
#28892: Re:延伸題


linlincaleb@gmail.com (臨末之頌)

學校 : 新北市立板橋高級中學
編號 : 132772
來源 : [111.248.111.135]
最後登入時間 ：
2023-04-01 22:41:13
h084. 4. 牆上海報 -- 2022年1月APCS | From: [203.64.161.154] | 發表日期 : 2022-01-10 12:34

同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？

二分搜+單調隊列+greedy

或是二分搜內DP

不對 應該不用單調隊列 

其實只要把海報高度存到vector 之後sort

每次二分搜的時候看看每一段有多長 把它們記錄下來，之後DP

 
#28894: Re:延伸題


cthbst (吳宗達)

學校 : 國立交通大學
編號 : 19791
來源 : [39.9.166.145]
最後登入時間 ：
2024-03-19 08:37:45
h084. 4. 牆上海報 -- 2022年1月APCS | From: [140.113.136.219] | 發表日期 : 2022-01-10 15:31

同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？


可以思考這個問題和 Subset Sum 問題、Bin Packing 問題的關聯性

這個延伸題應該是很有難度的

如果可以很快解這個延伸題，就可以很快的解 Subset Sum, Bin Packing 

 
#28895: Re:延伸題


r1cky (hehe)

學校 : 國立臺灣師範大學
編號 : 158637
來源 : [118.166.194.111]
最後登入時間 ：
2024-04-13 22:10:59
h084. 4. 牆上海報 -- 2022年1月APCS | From: [49.216.164.12] | 發表日期 : 2022-01-10 15:47

同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？


抱歉，當時我有想到一個greedy+二分搜做法，但後來討論後發現有特例，所以其實我也不知道有沒有快速的解（也許n要小一點），不過我覺得單調隊列有機會nlognlogC（logc指的是高度的二分搜），如果可以，這是可通過的解。

 
#28906: Re:延伸題


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.39.123]
最後登入時間 ：
2024-04-19 00:03:36
h084. 4. 牆上海報 -- 2022年1月APCS | From: [1.170.219.173] | 發表日期 : 2022-01-11 16:49

同樣是P4，輸入範圍不變，但是張貼不用照順序，也就是2可以貼在1的左邊，問你最大高度？


抱歉，當時我有想到一個greedy+二分搜做法，但後來討論後發現有特例，所以其實我也不知道有沒有快速的解（也許n要小一點），不過我覺得單調隊列有機會nlognlogC（logc指的是高度的二分搜），如果可以，這是可通過的解。


讓我想到這題：a455: TOI2010 第四題：商品特賣問題
每張海報長度可以視為需要被裝入箱中的物品重量，而每段連續的區間長度就是給定的ｎ種大小的箱子，雖然是最大化裝入箱的物品重量，但因為 M ≤ 50且 N ≤ 1000，morris1028 公開的方法是 IDDFS，對應回原題的限制範圍更大，但原 PO 的方法可以丟過來試試。

 
#28910: Re:延伸題


r1cky (hehe)

學校 : 國立臺灣師範大學
編號 : 158637
來源 : [118.166.194.111]
最後登入時間 ：
2024-04-13 22:10:59
h084. 4. 牆上海報 -- 2022年1月APCS | From: [49.216.41.236] | 發表日期 : 2022-01-12 07:26

讓我想到這題：a455: TOI2010 第四題：商品特賣問題

每張海報長度可以視為需要被裝入箱中的物品重量，而每段連續的區間長度就是給定的ｎ種大小的箱子，雖然是最大化裝入箱的物品重量，但因為 M ≤ 50且 N ≤ 1000，morris1028 公開的方法是 IDDFS，對應回原題的限制範圍更大，但原 PO 的方法可以丟過來試試。


我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。

 
#30585: Re: 延伸題


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
h084. 4. 牆上海報 -- 2022年1月APCS | From: [114.25.48.5] | 發表日期 : 2022-05-30 14:12

我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。


瑞1奇電電電orz

 
#30597: Re: 延伸題


linlincaleb@gmail.com (臨末之頌)

學校 : 新北市立板橋高級中學
編號 : 132772
來源 : [111.248.111.135]
最後登入時間 ：
2023-04-01 22:41:13
h084. 4. 牆上海報 -- 2022年1月APCS | From: [111.248.114.127] | 發表日期 : 2022-05-30 20:55

我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。


瑞1奇電電電orz

老鼠電電電orz

 
#30599: Re: 延伸題


lai.abc8660@gmail.com (alan lai)

學校 : 臺北市立成功高級中學
編號 : 81120
來源 : [180.176.149.15]
最後登入時間 ：
2023-12-18 22:49:26
h084. 4. 牆上海報 -- 2022年1月APCS | From: [180.176.149.15] | 發表日期 : 2022-05-30 21:52

我的看法是感覺DP在這裡不太可行（至少我現在沒有想到可以的方法），也許用圖論的觀點來看是比較容易的，至於題目範圍限制似乎不能這麼大，我是覺得有點難度。


瑞1奇電電電orz

老鼠電電電orz


linlinmorz

 
ZeroJudge Forum