→ walker2009:這題真的搞到頭暈 @_@ 04/21 18:59
推 walker2009:這個 case l大的作法會得到正確答案, 我還在試圖證明XD 04/21 19:18
→ walker2009:還沒看懂 l大的証明 Orz 04/21 19:18
hi bleed大，
測資：
10 10
10 20
5 21
8 21
7 21
1 21
您的程式跑出來的結果是 3
但此測資似乎可以疊出紅色部份為 4 ??
※ 引述《bleed1979 (十三)》之銘言：
: 將[一個感覺是 dynamic programming 的題目]做一個結論。
: D網友說得Prob_Solve的l網友用的是LIS，其實算是對的。
: l網友判斷依據在於LIS的第二個內for迴圈，以下將有程式架構和原因及程式碼。
: l網友的方法也是對的，因為在LIS的迭代過程中，
: 這方法就是將累積重量降到最低以方便後面的烏龜承受重量。
: (這裡說得對的，至少是能通過UVa的judge。不曉得有沒有更critical的測資。)
: 程式架構︰
: 1.將負載重量由小到大排序，當然重量要對應好。
: 2.LIS
: 配置累積重量陣列acc_weight。
: 配置二維的烏龜重量序列, 一開始都是空的。
: (這裡放得是烏龜的重量，不是第幾隻烏龜。)
: for ( 第i烏龜(i從第一隻開始)到最後一隻烏龜 )
: {
: if (acc_weight[i] == 0)
: {
: acc_weight[i] = 第i隻烏龜的重量
: 將第i隻烏龜的重量放入烏龜重量序列[i]
: }
: // 第一階段，判斷多一隻的情況
: for( j = 第i隻烏龜到最後一隻烏龜)
: {
: if (acc_weight[i] + 烏龜j重量 <= 烏龜j能負載的重量 並且
: 烏龜重量序列[i]的隻數 + 1 >= 烏龜重量序列[j]的隻數)
: {
: if (烏龜重量序列[i]的隻數 + 1 > 烏龜重量序列[j]的隻數)
: {
: 烏龜重量序列[j] = 烏龜重量序列[i]
: 再將烏龜j重量放入烏龜重量序列[j]
: acc_weight[j] = acc_weight[i] + 烏龜j的重量
: }
: else // 隻數i + 1 和隻數j 相等
: {
: if (acc_weight[j] == 0 或者
: acc_weight[j] > acc_weight[i] + 烏龜j重量)
: {
: 烏龜重量序列[j] = 烏龜重量序列[i]
: 再將烏龜j重量放入烏龜重量序列[j]
: acc_weight[j] = acc_weight[i] + 烏龜j的重量
: }
: }
: }
: }
: // 第二階段，將累積重量降到最低，同l網友的方法
: for( j = 第i隻烏龜到最後一隻烏龜)
: {
: if (烏龜重量序列[i]的隻數 == 烏龜重量序列[j]的隻數 並且
: 烏龜重量序列[i]裡最重的比烏龜j重量還要重)
: {
: 烏龜重量序列[j] = (烏龜重量序列[i] 扣掉 最重的烏龜)
: 再將烏龜j重量放入烏龜重量序列[j]
: acc_weight[j] = acc_weight[i] - 最重的烏龜 + 烏龜j的重量
: }
: }
: }
: 這裡就是測試通過的實做程式碼: http://nopaste.csie.org/c785a
: 為什麼要多做第二階段？
: 因為如果序列長度一樣，但累積重量可以比較小，
: 當然是換成累積重量比較小的序列，以方便之後的烏龜負載。
: 為什麼要和最重的比？
: 因為拿掉最重的相當於此序列瘦身最大的程度。減輕最多的意思。
: Bleed
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.248.4.114