題目 2510:
信息學(xué)奧賽一本通T1611-倉(cāng)庫(kù)建設(shè)
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 10 解決: 5
題目描述
原題來自：ZJOI 2007
L 公司在山上有一些工廠。由于這座山處于高原內(nèi)陸地區(qū)（干燥少雨），L 公司一般把產(chǎn)品直接堆放在露天，以節(jié)省費(fèi)用。突然有一天，L 公司的總裁 L 先生接到氣象部門的電話，被告知三天之后將有一場(chǎng)暴雨，于是 L 先生決定緊急在某些工廠建立一些倉(cāng)庫(kù)以免產(chǎn)品被淋壞。
L 公司在山上有一些工廠。由于這座山處于高原內(nèi)陸地區(qū)（干燥少雨），L 公司一般把產(chǎn)品直接堆放在露天，以節(jié)省費(fèi)用。突然有一天，L 公司的總裁 L 先生接到氣象部門的電話，被告知三天之后將有一場(chǎng)暴雨，于是 L 先生決定緊急在某些工廠建立一些倉(cāng)庫(kù)以免產(chǎn)品被淋壞。
L 公司在山上有 N 個(gè)工廠。如圖所示，工廠 1 在山頂，工廠 N 在山腳。
由于地形的不同，在不同工廠建立倉(cāng)庫(kù)的費(fèi)用可能不同。工廠 i 目前已有成品 Pi 件，在該廠建立倉(cāng)庫(kù)的費(fèi)用為 Ci 。對(duì)于沒有建立倉(cāng)庫(kù)的工廠，其產(chǎn)品應(yīng)被運(yùn)往其他的倉(cāng)庫(kù)進(jìn)行儲(chǔ)藏，而由于 L 公司產(chǎn)品的對(duì)外銷售處設(shè)置在山腳的工廠 N，故產(chǎn)品只能往山下運(yùn)（即只能運(yùn)往編號(hào)更大的工廠的倉(cāng)庫(kù)），當(dāng)然運(yùn)送產(chǎn)品也是需要費(fèi)用的，假設(shè)一件產(chǎn)品運(yùn)送 1 個(gè)單位距離的費(fèi)用是 1。假設(shè)建立的倉(cāng)庫(kù)容量都都是足夠大的，可以容下所有的產(chǎn)品。
已知：
1、工廠 i 距離工廠 1 的距離 Xi（其中 X1=0）；
2、工廠 i 目前已有成品數(shù)量 Pi ；
3、在工廠 i 建立倉(cāng)庫(kù)的費(fèi)用 Ci 。
請(qǐng)你幫助 L 公司尋找一個(gè)倉(cāng)庫(kù)建設(shè)的方案，使得總的費(fèi)用（建造費(fèi)用+運(yùn)輸費(fèi)用）最小。
輸入格式
第一行包含一個(gè)整數(shù) N，表示工廠的個(gè)數(shù)。
接下來 N 行，每行包含三個(gè)整數(shù) Xi,Pi,Ci ，意義如題中所述。
接下來 N 行，每行包含三個(gè)整數(shù) Xi,Pi,Ci ，意義如題中所述。
輸出格式
僅包含一個(gè)整數(shù)，為可以找到最優(yōu)方案的費(fèi)用。
樣例輸入
3 0 5 10 5 3 100 9 6 10
樣例輸出
32
提示
樣例說明
在工廠 1 和工廠 3 建立倉(cāng)庫(kù)，建立費(fèi)用為 10+10=20，運(yùn)輸費(fèi)用為 (9?5)×3=12，總費(fèi)用 32。如果僅在工廠 3 建立倉(cāng)庫(kù)，建立費(fèi)用為 10，運(yùn)輸費(fèi)用為 (9?0)×5+(9?5)×3=57，總費(fèi)用 67，不如前者優(yōu)。
數(shù)據(jù)范圍與提示：
對(duì)于全部數(shù)據(jù)，N≤106 ，保證所有的 Xi,Pi,Ci 均在 int 范圍以內(nèi)，保證中間計(jì)算結(jié)果不超過 long long 范圍。
在工廠 1 和工廠 3 建立倉(cāng)庫(kù)，建立費(fèi)用為 10+10=20，運(yùn)輸費(fèi)用為 (9?5)×3=12，總費(fèi)用 32。如果僅在工廠 3 建立倉(cāng)庫(kù)，建立費(fèi)用為 10，運(yùn)輸費(fèi)用為 (9?0)×5+(9?5)×3=57，總費(fèi)用 67，不如前者優(yōu)。
數(shù)據(jù)范圍與提示：
對(duì)于全部數(shù)據(jù)，N≤106 ，保證所有的 Xi,Pi,Ci 均在 int 范圍以內(nèi)，保證中間計(jì)算結(jié)果不超過 long long 范圍。