發表新討論
#28889:


r1cky (hehe)

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

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

 
#28890: Re:延伸題

Unknown User

h084. 4. 牆上海報 -- 2022年1月APCS | From: [203.64.161.154] | 發表日期 : 2022-01-10 12:29

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

二分搜+單調隊列+greedy

或是二分搜內DP

 
#28891: Re:延伸題

Unknown User

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
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
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
來源 : [1.163.213.15]
最後登入時間 ：
2024-10-22 08:34:42
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
來源 : [49.216.161.223]
最後登入時間 ：
2024-11-11 07:54:54
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
來源 : [49.216.18.187]
最後登入時間 ：
2024-11-10 10:25:04
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
來源 : [49.216.161.223]
最後登入時間 ：
2024-11-11 07:54:54
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.253.147]
最後登入時間 ：
2024-10-03 15:39:22
h084. 4. 牆上海報 -- 2022年1月APCS | From: [114.25.48.5] | 發表日期 : 2022-05-30 14:12

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


瑞1奇電電電orz

 
#30597: Re: 延伸題


linlincaleb@gmail.com (臨末之頌)

學校 : 新北市立板橋高級中學
編號 : 132772
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
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
來源 : [128.6.147.78]
最後登入時間 ：
2024-09-24 21:11:14
h084. 4. 牆上海報 -- 2022年1月APCS | From: [180.176.149.15] | 發表日期 : 2022-05-30 21:52

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


瑞1奇電電電orz

老鼠電電電orz


linlinmorz

 
ZeroJudge Forum