按一隻駱駝然後必須返回來計算,畢竟不能賣完水然後自己渴死在沙漠裡,也不能扔掉駱駝走回來……可以進行遞推,所有運到第k+1公里的水都必須先運到第k公里,將這些水額外再運一公里,需要:
注意這個次數是不考慮順序的,可以將水連續運若干公里,但其中的每瓶水都必須經過k到k+1這段距離。每運一次至少要2瓶水,而由於運量限制,一次最多運1050瓶,留下兩瓶路上使用。
設是如果在k公里的地方最多能賣的水的數量(也就是提前扣去返程需要的水之後剩下的),則將這些水儘量運到k+1公里的地方,只需要每次都滿載、運足夠次就可以。注意如果最後只剩下一瓶,那麼這一瓶是不夠支付返程費用的,只能將它丟在k公里的地方,如果有兩瓶則額外運一趟也只是當路費。這種情況可以特殊考慮。
總結來說,遞推式可以寫成:
初始條件
注意到由於初始值是個偶數,而從遞推式中我們可以看到,當是偶數時,由於取值的限制,它不可能模1050餘1,所以永遠適用上面一半的遞推式。當取值保持不變的時候,這一部分f的取值構成等差數列,不難計算出:
所以
運出586瓶水的方案,最簡單的就是按照遞推式的,每次運一公里,留下一瓶水做最後返程用,然後繼續往前運。考慮到不變時,向前運的次數不變,可以將這些向前運的次數合併起來,儘量運到次數改變的邊界上,也就是:
按一隻駱駝然後必須返回來計算,畢竟不能賣完水然後自己渴死在沙漠裡,也不能扔掉駱駝走回來……可以進行遞推,所有運到第k+1公里的水都必須先運到第k公里,將這些水額外再運一公里,需要:
若干次向前的一公里相同次數的回退一公里(包括最後賣完之後從k+1返回k)注意這個次數是不考慮順序的,可以將水連續運若干公里,但其中的每瓶水都必須經過k到k+1這段距離。每運一次至少要2瓶水,而由於運量限制,一次最多運1050瓶,留下兩瓶路上使用。
設是如果在k公里的地方最多能賣的水的數量(也就是提前扣去返程需要的水之後剩下的),則將這些水儘量運到k+1公里的地方,只需要每次都滿載、運足夠次就可以。注意如果最後只剩下一瓶,那麼這一瓶是不夠支付返程費用的,只能將它丟在k公里的地方,如果有兩瓶則額外運一趟也只是當路費。這種情況可以特殊考慮。
總結來說,遞推式可以寫成:
初始條件
注意到由於初始值是個偶數,而從遞推式中我們可以看到,當是偶數時,由於取值的限制,它不可能模1050餘1,所以永遠適用上面一半的遞推式。當取值保持不變的時候,這一部分f的取值構成等差數列,不難計算出:
所以
運出586瓶水的方案,最簡單的就是按照遞推式的,每次運一公里,留下一瓶水做最後返程用,然後繼續往前運。考慮到不變時,向前運的次數不變,可以將這些向前運的次數合併起來,儘量運到次數改變的邊界上,也就是:
將所有水分四次運到132公里處,每次去和回各自消耗132瓶水,並且最後一次到達132公里處時,留下132瓶水做最後返程用;剩下4200 - 132 * 4 * 2 = 3144瓶從132公里處,將3144瓶分三次運到306公里處,每次去和回各自消耗174瓶水,最後留下174瓶水在306公里處;剩下3144 - 174 * 3 * 2 = 2100瓶從306公里處,將2100瓶分兩次運到569公里處,每次去和回各自消耗263瓶水,最後留下263瓶水在569公里處;剩下2100 - 263 * 2 * 2 = 1048瓶從569公里處,將1048瓶一次運到800公里處,消耗231瓶,同時留下231瓶返程用,剩下586瓶可以賣掉賣掉586瓶,之後,利用之前留在各個位置的水返回