作者  bleed1979 (十三)                                       看板  C_and_CPP 
 標題  [ACM ] 10154 烏龜塔 解法                                               
 時間  Wed Apr 21 13:50:54 2010                                                 

2010.04.23 09:40 修訂二版

http://nopaste.csie.org/d3f4a

方法和一版是一樣的，可是跑出來結果卻不相同。


Bleed

======================================================================
2010.04.23 00:14 修訂一版

修訂一版程式碼︰http://nopaste.csie.org/c4691

1.僅將負載重量由小到大排序。

2.LIS精神 + 額外的替換烏龜。

配置一維累積重量陣列acc_weight，初始為0。
配置二維的烏龜重量序列, 一開始都是空的。
(這裡放得是烏龜的重量，不是第幾隻烏龜。)
配置一維烏龜重量序列中序列一定會有的烏龜重量的index。
(代表第i個序列，一定會有第i隻烏龜的重量，因為他至少會負載自己，
要把該index記起來，以防替代的時候不小心替代錯誤。)

2.1 跑一次for迴圈對i序列放入烏龜i的重量，
並且acc_weight[i] = weight[i],
一定會有的烏龜重量index為0。

2.2

for ( 第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的重量
        index要對應烏龜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的重量
          index要對應烏龜j
        }
      }
    }
  }
  else  // 第二判斷，做替換烏龜的動作。
  {
    如果烏龜i放進序列j裡面可以減輕序列j的累積重量，
    並且根據index判斷替換的烏龜並不是烏龜j(序列j裡面烏龜j一定要存在)，
    將烏龜i放入序列j裡，
    並拿掉最重的烏龜或次重的烏龜(烏龜j是最重的那就跟次重的比)。
    這段的實做請參閱程式碼。寫得並不太漂亮。
  }
}

原文程式的盲點在於，我忽略了序列j裡面烏龜j一定要存在。
所以之前替換掉了烏龜j且並未做判斷。
雖然AC，但是只是運氣好罷了。

目前這個程式可以AC也測試過了版上的測資。如果還有更critical的測資，我再做修訂。


Bleed

==============================================================================
將[一個感覺是 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: 114.32.177.97
→ scars:我來看熱鬧的
推 walker2009:嗚嗚,我已經習慣看英文變數了,中文變數看到頭昏(遮臉)
※ 編輯: bleed1979       來自: 114.32.177.97        (04/23 00:15)
※ 編輯: bleed1979       來自: 114.32.177.97        (04/23 00:29)
※ 編輯: bleed1979       來自: 114.32.177.97        (04/23 09:41)